这是一道欧拉回路的板子题，唯一的不同在于要输出是怎么在那几个环上转出的答案，这样就不能用邻接矩阵存图（其实本题的数据也直接否定了邻接矩阵存图的方法）
不断的在寻找一个简单环，并在它上转一次，相当于消掉一个环，并把所有路径记录在一个 stack 之中，在 stack 中一定会形成 这样一种路径 a.....a b......b c.......c因为最后一定会转回起点，所以可以倒序输出一个被同一终点起点包围的点
#include<bits/stdc++.h> using namespace std; int n,m; struct node{ int to,nxt; }e[2000010];int tot; int first[2000010]; int ind[2000010]; stack<int>sta; queue<int>q; int ans; inline void add_edge(int a,int b){ e[++tot].to=b,e[tot].nxt=first[a],first[a]=tot; e[++tot].to=a,e[tot].nxt=first[b],first[b]=tot; } inline int kd(){ int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+(ch^48);ch=getchar();} return x*f; } void dfsl(int x,int root){ ind[x]-=2;//因为正反两边都不能走了所以入度会减二 for(int i=first[x];i;i=e[i].nxt){ int to=e[i].to; if(e[i].to==0)continue; else{ e[i].to=e[((i-1)^1)+1].to=0; //正反两边都不能再走了，就破坏掉 if(to==root){ sta.push(to),sta.push(x); return; } dfsl(to,root); sta.push(x); return; } } } int main(){ n=kd(),m=kd(); for(int i=1;i<=m;i++){ int a=kd(),b=kd(),c=kd(),d=kd(); if(c==d)continue;//只有在不同时才有走这条边的必要 else{ add_edge(a,b); ind[a]++,ind[b]++;//添加边和增加入度 } } for(int i=1;i<=n;i++){ if(ind[i]&1){//如果有奇数入度的边一定是不会有欧拉回路的 cout<<"NIE"<<endl; return 0; } } for(int i=1;i<=n;i++){ if(ind[i]){ while(ind[i]){ dfsl(i,i); ans++; } } } printf("%d ",ans); int root; while(sta.empty()==false){ int now; now=sta.top(); sta.pop(); q.push(now); if(q.size()==1){//如果这是一个开始 root=q.front(); } else if(now==root){//如果陷入轮回，这是一个结束 cout<<q.size()-1<<" "<<now<<" ";q.pop(); while(q.empty()==false)cout<<q.front()<<" ",q.pop();//循环输出在队列里保存好的路径 puts(""); } } return 0; }