这题要求每条边正反各被走一次，求一条路径。
每条边正反各走一次的话，对度数就没有要求了，即任意图都可构造出一条题意路径。
打印过程类似欧拉回路的过程，dfs时记录经过点数。不过这里vis标记只标记访问的单向边。
/* 必须满足所有度数都为偶数 有且仅有2个度数为奇数时，存在欧拉路径 */ #include<bits/stdc++.h> using namespace std; const int M =2e5+7; int head[M],cnt; struct EDGE{int to,nxt;}ee[M*2]; void add(int x,int y){ee[++cnt].nxt=head[x],ee[cnt].to=y,head[x]=cnt;} int st[M],ans[M],du[M],pr[M]; bool vis[M]; int n,m,top,t; void euler() { st[++top]=1; while(top>0) { // cout<<"- "<<st[top]<<endl; int x=st[top],i=head[x]; while(i&&vis[i])i=ee[i].nxt; if(i) { st[++top]=ee[i].to; vis[i]=true; head[x]=ee[i].nxt; } else { top--; ans[++t]=x; } } } int main() { cin>>n>>m; cnt=1; for(int i=1;i<=m;i++) { int u,v; scanf("%d%d",&u,&v); add(u,v),add(v,u); du[v]++,du[u]++; } euler(); for(int i=1;i<=t;i++)printf("%d\n",ans[i]); return 0; }
