小码匠的信息学江湖:【模板】欧拉路径

4 6
1 3
2 1
4 2
3 3
1 2
3 4

1 2 1 3 3 4 2

5 5
1 2
3 5
4 3
3 4
2 3

1 2 3 4 3 5

4 3
1 2
1 3
1 4

No

// Copyright (C) 2021-2028 coder-oldgeek.com All rights reserved.
// 题目: 【模板】欧拉路径
// 链接: https://www.luogu.com.cn/problem/P7771
// 难度: 普及+/提高
// 提交:
// 题解：
// - https://www.luogu.com.cn/problem/solution/P7771
#include <bits/stdc++.h>

using namespace std;

#define endl '\n';

const int MAXN = 100010;
int vis[MAXN];

struct node {
    int in, out;
} degree[MAXN];

stack<int> st;
vector<int> g[MAXN];

void dfs(int now) {
    for (int i = vis[now]; i < g[now].size(); i = vis[now]) {
        vis[now] = i + 1;
        dfs(g[now][i]);
    }
    st.push(now);
}

void best_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        ++degree[v].in;
        ++degree[u].out;
    }
    for (int i = 1; i <= n; ++i) {
        sort(g[i].begin(), g[i].end());
    }
    int s = 1;
    pair<int, int> cnt = {0, 0};
    bool is = true;
    for (int i = 1; i <= n; ++i) {
        if (degree[i].in != degree[i].out) {
            is = false;
            if (degree[i].out - degree[i].in == 1) {
                ++cnt.second;
                s = i;
            } else if (degree[i].in - degree[i].out == 1) {
                ++cnt.first;
            } else {
                cout << "No";
                return;
            }
        }
    }
    if ((!is) && !(cnt.first == cnt.second && cnt.first == 1)) {
        cout << "No";
        return;
    }
    dfs(s);
    while (!st.empty()) {
        cout << st.top() << " ";
        st.pop();
    }
}

void happy_coder() {
    // 提升cin、cout效率
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
}

int main() {
    // 小码匠
    best_coder();

    // 最优解
    // happy_coder();

    // 返回
    return 0;
}