题解
链式前向星版本的欧拉回路dfs
void dfs(int u){ for (int i=head[u];i>0;i=head[u]){ head[u]=Next[i]; //走过的路直接跳过 dfs(to[i]); } que[l++]=u; }
接下来的难点是如何字典序搜索。我们在dfs的时候直接让走字典序最小的边即可;而由于链式前向星是从后往前枚举的,我们需要对所有的边进行排序。
bool cmp(Node a,Node b){ if (a.u!=b.u) return a.u<b.u; return a.v>b.v; //保证每次枚举都是字典序最小的边 }
code
#include<bits/stdc++.h> using namespace std; const int N=1e5+5; const int M=2e5+5; int head[N],Next[M],to[M],in[N],out[N]; struct Node{ int u,v; }; Node a[M]; bool cmp(Node a,Node b){ if (a.u!=b.u) return a.u<b.u; return a.v>b.v; } int cnt=1,l=0; int que[M]; void build(int i){ Next[cnt]=head[a[i].u]; to[cnt]=a[i].v; head[a[i].u]=cnt++; } void dfs(int u){ for (int i=head[u];i>0;i=head[u]){ head[u]=Next[i]; // cout<<u<<" "<<to[i]<<endl; dfs(to[i]); } que[l++]=u; } int main(){ int n,m; cin>>n>>m; for (int i=1;i<=m;i++){ cin>>a[i].u>>a[i].v; in[a[i].v]++; out[a[i].u]++; } int n1=0,n2=0,start=1,end=n; for (int i=1;i<=n;i++){ if (in[i]-out[i]==1){ n1++; end=i; continue; } if (out[i]-in[i]==1){ n2++; start=i; continue; } if (in[i]!=out[i]){ cout<<"No\n"; return 0; } } if ((n1==0 && n2==0) || (n1==1 && n2==1)){ sort(a+1,a+m+1,cmp); // for (int i=1;i<=m;i++) cout<<a[i].u<<" "<<a[i].v<<endl; for (int i=1;i<=m;i++) build(i); dfs(start); while (l){ if (l) cout<<que[--l]<<" "; else cout<<que[--l]; } } else cout<<"No\n"; return 0; }
标签:Node,head,P7771,int,cnt,dfs,Next,模板,欧拉 From: https://www.cnblogs.com/purple123/p/18117539