求欧拉回路( dfs )
#include <bits/stdc++.h> using namespace std ; const int N=1e6+3,M=2e6+3; inline int read(){ int res = 0, flag = 1; char ch = getchar(); while (ch < '0' || ch > '9') { if (ch == '-') flag = -1; ch = getchar(); } while (ch >= '0' && ch <= '9') { res = res * 10 + ch - '0'; ch = getchar(); } return res * flag; } int n,m; // op==1 有向图 op==2 无向图 vector<int> ans; int deg[N],in[N],out[N]; int nxt[M],go[M],hd[N],all; int op; int vis[N]; void add_(int x,int y){ nxt[++all]=hd[x]; hd[x]=all; go[all]=y; } void dfs(int x){ for(int &i=hd[x];i;i=nxt[i]){ int y=go[i]; int k=i; if(op==1){ int e=(i+1)/2; if(vis[e]==0){ vis[e]=1; dfs(y); if(k&1) ans.push_back(e); else ans.push_back(-e); } } else{ if(vis[k]==0){ vis[k]=1; dfs(y); ans.push_back(k); } } } } signed main(){ int i,x,y; scanf("%d%d%d",&op,&n,&m); for(i=1;i<=m;i++){ x=read(),y=read(); if(op==1){ add_(x,y),add_(y,x); deg[x]++,deg[y]++; } else{ add_(x,y); out[x]++,in[y]++; } } if(op==1){ for(i=1;i<=n;i++) if(deg[i]&1){ printf("NO\n"); return 0; } } else{ for(i=1;i<=n;i++){ if(in[i]!=out[i]){ printf("NO\n"); return 0; } } } for(i=1;i<=n;i++){ if(hd[i]){ dfs(i); break; } } if(ans.size()==m){ cout<<"YES"<<endl; for(i=ans.size()-1;i>=0;i--) printf("%d ",ans[i]); } else{ cout<<"NO\n"; } }
标签:ch,vis,int,dfs,3.7,hd,ans,10105,欧拉 From: https://www.cnblogs.com/towboa/p/17133653.html