P7771 欧拉路径 题解
思路
欧拉路径的性质在于，起点入度比出度少一（图是一个环除外），终点出度比入度少一（图是一个环除外），其它点的入度和出度相等。
所以我们只要先用 \(O(m)\) 读入边，再 \(O(n)\) 判定是否有起点和终点即可。值得注意的是，因为欧拉路径每条边必须走且只能走一次，我们有必要在存边的时候，同时存储边的编号。
最后我们可以直接 DFS，对于每次搜到的点，选择一条没有走过的边继续走。把所有的结果压进栈里，最后按顺序弹出来就是一条欧拉路径。
因为要求字典序最小，可以先对一个点所有可以到的点排序，每次选编号尽量小的点走。
细节
2.1 读入与存储
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
outs[x]++;
ins[y]++;
p[x].push_back(make_pair(y,i));
}
使用vector进行存边，可以方便我们之后进行排序。因为pair是以第一项为第一关键字的，所以我们把点的编号放在第一项，边的编号放在第二项。
2.2 判定欧拉路径的存在
int s=INT_MAX,f=INT_MAX;
for(int i=1;i<=n;i++){
if(ins[i]!=outs[i]){
num++;
}
if(ins[i]==outs[i]-1){
s=i;
}
if(outs[i]==ins[i]-1){
f=i;
}
}
if(num!=0&&num!=2){
cout<<"No"<因为欧拉路径当中只有起点和终点入度不等于出度（起点和终点在一个环上除外），所以可以分三种情况：
- 有 \(2\) 个点的入度和出度不同：普通的欧拉路径。
- 有 \(0\) 个点的入度和出度不同：起点和终点在环上，把起点和终点都设置为 \(1\)。
- 其它的情况：不存在欧拉路径，输出
No。
2.3 DFS
void DFS(int x){
for(int i=0;i用一个数组描述一条边是否走过。如果没有走过这条边，就将这条边的标记改为走过并继续 DFS 这条边连向的点。
最后要记得把走过的点推入栈中。
但是这种办法的复杂度可以被 \(10^5\) 条 \(1\rightarrow 2\) 的边与 \(10^5\) 条 \(2 \rightarrow 1\) 的边所构成的图卡成 \(O(m^2)\) 的高复杂度。所以我们不妨用一个数组记录下一次到这个点时应该搜第几条边，下次从这条被记录边继续搜而不用全部重新搜一次。
修改后的 DFS 如下：
void DFS(int x){
for(int i=nexto[x];i2.4 输出
while(!q.empty()){
cout<把栈里的东西依次输出即可。
AC code
各部分已经分解放在文中。
AC记录