求一个无向图的欧拉回路,但要求每条边正反过一次
当作有向图,打标记只打一条边
#include <iostream> #include <algorithm> #include <cstring> #include <stack> using namespace std ; const int N= 1e5+3,M=N; stack<int> st; int all,nxt[M],go[N],hd[N]; int n,m,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]; if(vis[i]==0) vis[i]=1,dfs(y),st.push(x); } } signed main(){ int i,a,b; while(cin>>n>>m){ for(i=1;i<=n;i++) hd[i]=0; all=0; while(st.empty()==0) st.pop(); for(i=1;i<=m;i++){ cin>>a>>b; add_(a,b);add_(b,a); } dfs(1); while(st.empty()==0){ cout<< st.top() <<endl; st.pop(); } cout<<1<<endl; } }
标签:int,2230,dfs,vis,poj,go,include,hd From: https://www.cnblogs.com/towboa/p/17134670.html