洛谷 P7771：【模板】欧拉路径

【题目来源】
https://www.luogu.com.cn/problem/P7771

【题目描述】
求有向图字典序最小的欧拉路径。

【输入格式】
第一行两个整数 n,m 表示有向图的点数和边数。
接下来 m 行每行两个整数 u,v 表示存在一条 u→v 的有向边。

【输出格式】
如果不存在欧拉路径，输出一行 No。
否则输出一行 m+1 个数字，表示字典序最小的欧拉路径。

【输入样例】
4 6
1 3
2 1
4 2
3 3
1 2
3 4

【输出样例】
1 2 1 3 3 4 2

【说明/提示】
对于 50% 的数据，n,m≤10^3。
对于 100% 的数据，1≤u,v≤n≤10^5，m≤2×10^5。
保证将有向边视为无向边后图连通。

【算法分析】
● 欧拉路径与欧拉回路定义
图中经过所有边恰好一次的路径称为欧拉路径（也就是一笔画）。
如果此路径的起点和终点相同，则称其为欧拉回路。
注意：若存在欧拉回路，则一定存在欧拉路径。

● 欧拉路径判定
（1）有向图欧拉路径：图中恰好存在 1 个结点的出度比入度多 1（这个结点即为起点 S），1 个结点的入度比出度多 1（这个结点即为终点 T），其余结点的出度=入度。
（2）有向图欧拉回路：所有结点的入度=出度（起点 S 和终点 T 可以为任意点）。
（3）无向图欧拉路径：图中恰好存在 2 个结点的度是奇数，其余结点的度为偶数，这两个度为奇数的结点即为欧拉路径的起点 S 和终点 T。
（4）无向图欧拉回路：所有结点的度都是偶数（起点 S 和终点 T 可以为任意结点）。

● 欧拉路径与欧拉序的区别
欧拉序：https://blog.csdn.net/hnjzsyjyj/article/details/139674161

【算法代码】

#include<bits/stdc++.h>
using namespace std;

const int maxn=1e5+5;
vector<int> g[maxn];
int ind[maxn];
int ne[maxn];
stack<int> ans;

void dfs(int u) {
    int i=ne[u];
    while(i<g[u].size()) {
        ne[u]=i+1;
        dfs(g[u][i]);
        i=ne[u];
    }
    ans.push(u);
}

int main() {
    int n,m;
    cin>>n>>m;
    for(int i=1; i<=m; i++) {
        int x,y;
        cin>>x>>y;
        g[x].push_back(y);
        ind[y]++;
    }

    int sp=1; //starting point
    int out=0,in=0;
    for(int i=1; i<=n; i++) {
        sort(g[i].begin(),g[i].end());
        int cnt=g[i].size();
        if(ind[i]==cnt-1) out++,sp=i;
        else if(ind[i]==cnt+1) in++;
        else if(cnt!=ind[i]) {
            cout<<"No"<<endl;
            return 0;
        }

        if(in>1 || out>1) {
            cout<<"No"<<endl;
            return 0;
        }
    }

    dfs(sp);
    while(ans.size()) {
        cout<<ans.top()<<" ";
        ans.pop();
    }

    return 0;
}

/*
in:
4 6
1 3
2 1
4 2
3 3
1 2
3 4

out:
1 2 1 3 3 4 2
*/

【参考文献】
https://www.luogu.com.cn/problem/solution/P7771
https://blog.csdn.net/hnjzsyjyj/article/details/139674161
https://www.cnblogs.com/pure4knowledge/p/18115374