题意

给你一个有向图或无向图，要求输出其中一条欧拉回路。
$n\le100000$

分析

圈套圈算法求欧拉回路的模版题。
这个算法大概是，从某个点开始走，然后用一个栈存放所有走过的点。当走到死胡同时就退栈，直到退到某个点仍然存在出边，然后继续沿着出边走下去。
这可以看成是先找到一个环，然后再找到另一个环，接着把这两个环拼在一起，就形成了一个更大的环。不停的操作下去，就可以得到极大环也就是欧拉回路了。

代码

#include
#include
#include
#include
#includeconst int N=100005;int ty;struct Task1
{int n,m,cnt,last[N],deg[N],f[N],stack[N*2],num[N*2],ans[N*2],tot;struct edge{int to,next,id;bool use;}e[N*4];void addedge(int u,int v){e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt;}int find(int x){if (f[x]==x) return x;else return f[x]=find(f[x]);}void work(){int top=0,s;for (int i=1;i<=n;i++) if (deg[i]) {s=i;break;}stack[++top]=s;while (top){int x=stack[top];while (e[last[x]].use) last[x]=e[last[x]].next;if (last[x]){stack[++top]=e[last[x]].to;num[top]=(last[x]&1)?-last[x]/2:last[x]/2;e[last[x]].use=e[last[x]^1].use=1;last[x]=e[last[x]].next;}else{while (top&&!last[stack[top]]){if (top>1) ans[++tot]=num[top];top--;}}}while (tot) printf("%d ",ans[tot]),tot--;}void solve(){scanf("%d%d",&n,&m);cnt=1;for (int i=1;i<=n;i++) f[i]=i;int sum=n;for (int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addedge(x,y);deg[x]++;deg[y]++;if (find(x)!=find(y)) f[find(x)]=find(y),sum--;}for (int i=1;i<=n;i++) if (!deg[i]) sum--;if (sum>1) {puts("NO");return;}for (int i=1;i<=n;i++) if (deg[i]&1) {puts("NO");return;}puts("YES");work();}
}t1;struct Task2
{int n,m,cnt,f[N],rd[N],cd[N],last[N],stack[N*2],num[N*2],ans[N*2],tot;struct edge{int to,next,id;}e[N*2];void addedge(int u,int v){e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt;}int find(int x){if (f[x]==x) return x;else return f[x]=find(f[x]);}void work(){int top=0,s;for (int i=1;i<=n;i++) if (cd[i]) {s=i;break;}stack[++top]=s;while (top){int x=stack[top];if (last[x]){stack[++top]=e[last[x]].to;num[top]=last[x];last[x]=e[last[x]].next;}else{while (top&&!last[stack[top]]){if (top>1) ans[++tot]=num[top];top--;}}}while (tot) printf("%d ",ans[tot]),tot--;}void solve(){scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) f[i]=i;int sum=n;for (int i=1;i<=m;i++){int x,y;scanf("%d%d",&x,&y);addedge(x,y);rd[y]++;cd[x]++;if (find(x)!=find(y)) f[find(x)]=find(y),sum--;}for (int i=1;i<=n;i++) if (!rd[i]&&!cd[i]) sum--;if (sum>1) {puts("NO");return;}for (int i=1;i<=n;i++) if (rd[i]!=cd[i]) {puts("NO");return;}puts("YES");work();}
}t2;int main()
{scanf("%d",&ty);if (ty==1) t1.solve();else t2.solve();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！