写了一道欧拉回路的模板题。先判断是否是欧拉回路，有向图和无向图有一点点不同，然后就是特判独立点的存在。

之后是输出路径，和dls学的dfs，利用last数组的更新可以做到线性的复杂度，否则一不小心就会写成m^2的复杂度

附上代码——by VANE

1 #include
      
         2 using namespace std;  3 int t,n,m;  4 const int N=100005;  5 int l,last[N],pre[N<<2],other[N<<2],f[N];  6 int rd[N],cd[N];  7 int getfa(int x)  8 {  9     return x==f[x]?x:f[x]=getfa(f[x]); 10 } 11 bool not_lone[N]; 12 bool vis[N<<2]; 13 void add(int a,int b,int c) 14 { 15     if(c==1) 16     {++l;pre[l]=last[a];last[a]=l;other[l]=b;} 17     else  18     {
    int L=l+m;pre[L]=last[a];last[a]=L;other[L]=b;} 19 } 20 void merge(int x,int y) 21 { 22     int fx=getfa(x),fy=getfa(y); 23     if(fx!=fy) 24     f[fx]=fy; 25 } 26 int abs(int x) 27 { 28     return x<=m?x:x-m; 29 } 30 int val(int x) 31 { 32     return x<=m?x:m-x; 33 } 34 stack
       
         sk; 35 void dfs(int x) 36 { 37     for(int p=last[x];p;p=last[x]) 38     { 39         while(vis[abs(p)]&&p) p=pre[p]; 40         last[x]=p; 41         if(p) 42         {     43             vis[abs(p)]=1; 44             dfs(other[p]);     45             sk.push(val(p)); 46         } 47     } 48  49 } 50 int main() 51 { 52     scanf("%d%d%d",&t,&n,&m); 53     for(int i=1;i<=n;++i) f[i]=i; 54     for(int i=1;i<=m;++i) 55     { 56         int x,y;scanf("%d%d",&x,&y); 57         add(x,y,1);if(t==1) add(y,x,m); 58         cd[x]++;rd[y]++; 59         not_lone[x]=not_lone[y]=1; 60         merge(x,y); 61     } 62     int rt=0; 63     for(int i=1;i<=n;++i) 64     { 65         if(not_lone[i]) 66         { 67             rt=i;break; 68         } 69     } 70     for(int i=1;i<=n;++i) 71     if(not_lone[i]&&getfa(i)!=getfa(rt)) 72     { 73         puts("NO"); 74         return 0; 75     } 76     if(t==1) 77     { 78         for(int i=1;i<=n;++i) 79         if((rd[i]+cd[i])&1) 80         {puts("NO");return 0;} 81     } 82     else 83     { 84         for(int i=1;i<=n;++i) 85         if(rd[i]!=cd[i]) 86         {puts("NO");return 0;} 87     } 88     for(int i=1;i<=n;++i) 89     if(not_lone[i]) 90     { 91         dfs(i); 92         break; 93     } 94     puts("YES"); 95     while(!sk.empty()) 96     { 97         printf("%d ",sk.top()); 98         sk.pop(); 99     }100 }
       
      

 

下面的By：大奕哥

我们就直接搜索啦，对于无向图需要保证的性质是任何点的出度+入度都要为偶数，对于有向图任意点的出度都要等于入度。

搜索就是一个回溯的过程，然后每次我们都把边删掉（head[x]=i)

然后如果要是能搜的话我们就加入队列。

在这里要特别注意对于孤立点（无任何边连入无任何边连出）的点，搜索从任意一个连边的点即可。

1 #include
     
       2 using namespace std; 3 const int N=500005; 4 int n,m,top,cnt,f[N],head[N],d1[N],d2[N],q[N]; 5 struct node 6 { 7     int to,nex,w; 8 }e[N<<1]; 9 void add(int x,int y,int w)10 {11     e[++cnt].to=y;e[cnt].nex=head[x];12     head[x]=cnt;e[cnt].w=w;13     d1[x]++;d2[y]++;14 }15 void dfs(int x)16 {17     for(int i=head[x];i;i=head[x])18     {19         while(i&&f[abs(e[i].w)])i=e[i].nex;20         head[x]=i;21         if(i)22         {23             f[abs(e[i].w)]=1;24             dfs(e[i].to);25             q[++top]=e[i].w;26         }27     }28 }29 int main()30 {31     int n,m,x,y,p,k;32     scanf("%d%d%d",&p,&n,&m);33     for(int i=1;i<=m;++i)34     {35         scanf("%d%d",&x,&y);36         add(x,y,i);37         if(p==1)add(y,x,-i);38     }39     for(int i=1;i<=n;++i)if(p==1&&d1[i]%2||p==2&&d1[i]!=d2[i]){puts("NO");return 0;}40     dfs(x);41     if(top