对刚学的欧拉回路的练习。
错点：
- 万一是欧拉路径不是欧拉回路的话，不能只选一个最小的点当起点。要选度数为奇数的两个点中较小的一个。
- \(1\)不一定在连通图内，不能单纯的把\(1\)当做起点。
3.见代码中的注释。
#include#include #include #include using namespace std;const int N = 5005;int m,n,head[N],tot,tmp[N],t,ans[N];int st[N],top,s=2e9,du[N];bool vis[N];struct edge{ int node,next;}e[N<<1];void add(int x,int y){ e[++tot].node=y; e[tot].next=head[x]; head[x]=tot;}int main(){ scanf("%d",&m); int x,y; tot=1;//漏掉了tot=1; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); add(x,y); add(y,x); du[x]++; du[y]++; s=min(s,min(x,y)); } for(int i=1;i<=500;i++) if(du[i]&1) { s=i; break; } st[++top]=s; while(top>0) { int u=st[top],i=head[u]; while(i&&vis[i]) i=e[i].next; if(!i) { --top; ans[++t]=u; } else { int tt=0; for(i=head[u];i;i=e[i].next) if(!vis[i]) tmp[++tt]=e[i].node; sort(tmp+1,tmp+tt+1); st[++top]=tmp[1]; for(i=head[u];i;i=e[i].next) if(e[i].node==tmp[1]&&!vis[i]) { vis[i]=vis[i^1]=1; break; }//这里找到一个就要break,因为如果有重边的话所有的与tmp[1]相连的边都会被标记 } } for(int i=t;i;i--) printf("%d\n",ans[i]); return 0;}