一道欧拉路径（回路）板子题。
注意“回路”那个词，那是第一个数据点。。。
没有特判没有找到起点的情况的话，这个点就没有分……
一般用链前做，但是由于这道题要求字典序，所以只能用matrix（邻接矩阵）。
下面上邻接矩阵的代码：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; #define maxn 3000 int g[maxn][maxn],d[maxn],st[maxn]; bool vis[maxn]; int n,ma,mi=99999,cnt=-1,top=-1,s; void dfs(int u) { for(int i=mi;i<=ma;i++) if(g[u][i]) { if(vis[i]) continue; g[u][i]--; g[i][u]--; dfs(i); st[++top]=i; } } int main() { scanf("%d",&n); for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); g[a][b]++; g[b][a]++; d[a]++; d[b]++; ma=max(ma,max(a,b)); mi=min(mi,min(a,b)); } for(int i=mi;i<=ma;i++) if(d[i]%2) { s=i; break; } if(s==0) s=mi; dfs(s); printf("%d\n",s); top++; while(top--) printf("%d\n",st[top]); return 0; }
下面是链前代码：
#include<cstdio> #include<iostream> #include<cstring> #include<algorithm> using namespace std; #define maxn 3000 int head[maxn],to[maxn],nxt[maxn],d[maxn],st[maxn]; bool vis[maxn]; int n,ma,mi=99999,cnt=-1,top=-1,s; void dfs(int u) { for(int i=head[u];i!=-1;i=nxt[i]) { if(vis[i]) continue; vis[i]=1; vis[i^1]=1; dfs(to[i]); st[++top]=to[i]; } } void add(int a,int b) { to[++cnt]=b; nxt[cnt]=head[a]; head[a]=cnt; } int main() { memset(head,-1,sizeof(head)); memset(nxt,-1,sizeof(nxt)); scanf("%d",&n); for(int i=1;i<=n;i++) { int a,b; scanf("%d%d",&a,&b); add(a,b); add(b,a); d[a]++; d[b]++; ma=max(ma,max(a,b)); mi=min(mi,min(a,b)); } for(int i=mi;i<=ma;i++) if(d[i]%2) { s=i; break; } if(!s) s=mi; dfs(s); printf("%d\n",s); top++; while(top--) printf("%d\n",st[top]); return 0; }
大同小异~
原文：https://www.cnblogs.com/popo-black-cat/p/10305510.html