[UOJ117] 欧拉回路

描述

有一天一位灵魂画师画了一张图，现在要你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

一共两个子任务：

这张图是无向图。（50分）
这张图是有向图。（50分）

输入格式

第一行一个整数

第二行两个整数

接下来

如果
如果

图中可能有重边也可能有自环。

输出格式

如果不可以一笔画，输出一行 “NO”。

否则，输出一行 “YES”，接下来一行输出一组方案。

如果
如果

样例一

input

output

YES
1 2 -3

样例二

input

output

YES
4 1 3 5 2 6

限制与约

时间限制：

 1 #include <cstdio>
 2 #include <cstring>
 3 using namespace std;
 4 #define maxn 100010
 5 #define maxm 400010
 6 struct edge{
 7     int v;
 8     bool ban;
 9     edge *nxt;
10 }ep[maxm];
11 int t,n,m,ecnt,cnt,ind[maxn],outd[maxn],ans[maxm];
12 edge *g[maxn];
13 inline void addedge(int u,int v){
14     edge *p=&ep[ecnt++];
15     p->v=v; p->ban=false; p->nxt=g[u];
16     g[u]=p;
17 }
18 inline edge* rev(edge *j){
19     int i=j-ep;
20     return ep+(i^1);
21 }
22 void dfs_ud(int i){
23     while (g[i])
24         if (!g[i]->ban){
25             edge *j=g[i];
26             j->ban=true;
27             rev(j)->ban=true;
28             dfs_ud(j->v);
29             int tmp=j-ep;
30             if(tmp&1) tmp=-(tmp/2+1);
31             else tmp=tmp/2+1;
32             ans[cnt++]=tmp;
33         }
34         else g[i]=g[i]->nxt;
35 }
36 void dfs_d(int i){
37     while (g[i])
38         if (!g[i]->ban){
39             edge *j=g[i];
40             j->ban=true;
41             dfs_d(j->v);
42             ans[cnt++]=j-ep+1;
43         }
44         else g[i]=g[i]->nxt;
45 }
46 int main(){
47     scanf("%d%d%d",&t,&n,&m);
48     ecnt=0;
49     memset(g,0,sizeof(g));
50     memset(ind,0,sizeof(ind));
51     memset(outd,0,sizeof(outd));
52     for (int i=0;i<m;++i){
53         int u,v;
54         scanf("%d%d",&u,&v);
55         --u,--v;
56         addedge(u,v);
57         ++outd[u];++ind[v];
58         if (t==1) addedge(v,u),++outd[v],++ind[u];
59     }
60     cnt=0;
61     if (t==1){
62         bool flag=true;
63         for (int i=0;i<n;++i)
64             if(ind[i]&1){flag=false;break;}
65         if(!flag) puts("NO");
66         else{
67             for(int i=0;i<n;++i){
68                 dfs_ud(i);
69                 if (cnt) break;
70             }
71             if (cnt==m){
72                 puts("YES");
73                 for (int i=cnt-1; i>=0; --i) printf("%d ",ans[i]);
74                 puts("");
75             }
76             else puts("NO");
77         }
78     }
79     else{
80         edge *p=g[0];
81         while (p) p=p->nxt;
82         bool flag=true;
83         for(int i=0;i<n;++i) if(ind[i]!=outd[i]){flag=false;break;}
84         if (!flag) puts("NO");
85         else{
86             for(int i=0;i<n;++i){
87             dfs_d(i);
88             if(cnt) break;
89             }
90             if(cnt==m){
91                 puts("YES");
92                 for(int i=cnt-1;i>=0;--i) printf("%d ",ans[i]);
93                 puts("");
94             }
95             else puts("NO");
96         }
97     }
98     return 0;
99 }

手动copy的代码，根本看不懂大佬在干嘛呀。

[UOJ117] 欧拉回路

描述

输入格式

输出格式

样例一

input

output

样例二

input

output

限制与约定 1≤n≤105,0≤m≤2×105

思路

代码实现

限制与约