题意：给定一个无向图G，输出一条路径，从1出发最后回到1，并使每条边都恰好从正反各经过一次。若有多解，输出一解即可。
思路：欧拉回路板子。此处采用邻接表做法，若当前遍历到点u的边i，则边i之前的边都已经被遍历过了，为了防止重复遍历造成的时间浪费，每次遍历后将head[u]更新为next[i]。
#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=10000+100,M=50000+100; struct node{ int to,nxt; }e[M<<1]; int head[N],tot=1; void add(int u,int v){ e[++tot]=(node){v,head[u]}; head[u]=tot; } bool vis[M<<1]; void dfs(int u){ for(int i=head[u];i;i=e[i].nxt){ if(!vis[i]){ int v=e[i].to; vis[i]=1; head[u]=e[i].nxt; dfs(v); } } printf("%d\n",u); } int main(){ int n,m; scanf("%d%d",&n,&m); for(int i=1;i<=m;i++){ int u,v; scanf("%d%d",&u,&v); add(u,v); add(v,u); } dfs(1); return 0; }
原文：https://www.cnblogs.com/Loi-Brilliant/p/9124361.html