UOJ #117. 欧拉回路

#117. 欧拉回路

分析：
　　直接dfs一遍，复杂度O(N+M)。注意类似dinic的当前弧优化，双向边标记两条。
　　sigongzi和mrclr的博客，关于欧拉回路以及此题文章。
　　有关欧拉路的总结。
代码：
 1 /*
 2 * @Author: mjt
 3 * @Date:   2018-10-16 17:34:46
 4 * @Last Modified by:   mjt
 5 * @Last Modified time: 2018-10-16 19:02:44
 6 */
 7 #include<cstdio>
 8 #include<algorithm>
 9 #include<cstring>
10 #include<cmath>
11 #include<iostream>
12 #include<cctype>
13 #include<set>
14 #include<vector>
15 #include<queue>
16 #include<map>
17 #define fi(s) freopen(s,"r",stdin);
18 #define fo(s) freopen(s,"w",stdout);
19 using namespace std;
20 typedef long long LL;
21 
22 inline int read() {
23     int x=0,f=1;char ch=getchar();for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
24     for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';return x*f;
25 }
26 
27 const int N = 200005;
28 
29 int head[N], nxt[N << 1], to[N << 1], En;
30 int deg[N], ans[N], cnt;
31 bool vis[N << 1];
32 
33 void add_edge(int u,int v) {
34     ++En; to[En] = v; nxt[En] = head[u]; head[u] = En;
35 }
36 
37 void dfs1(int u) {
38     for (int &i=head[u]; i; i=nxt[i]) {
39         int tmp = i;
40         if (!vis[tmp]) { // 不能直接用i，因为递归中可能改变了i
41             vis[tmp] = vis[tmp ^ 1] = true;
42             dfs1(to[tmp]);
43             ans[++cnt] = (tmp & 1) ? -(tmp >> 1) : (tmp >> 1);
44         }
45     }
46 }
47 
48 void solve1() { // 无向图
49     En = 1;
50     int n = read(), m = read(), s = 0;
51     for (int i=1; i<=m; ++i) {
52         int u = read(), v = read();
53         add_edge(u, v); add_edge(v, u);
54         deg[v] ++; deg[u] ++; s = u;
55     }
56     for (int i=1; i<=n; ++i) // 度数为偶数
57         if (deg[i] & 1) { puts("NO"); return ; }
58     dfs1(s);
59     if (cnt < m) puts("NO");
60     else { puts("YES"); for (int i=cnt; i>=1; --i) printf("%d ", ans[i]); }
61 }
62 
63 void dfs2(int u) {
64     for (int &i=head[u]; i; i=nxt[i]) {
65         int tmp = i;
66         if (!vis[tmp]) {
67             vis[tmp] = true;
68             dfs2(to[tmp]);
69             ans[++cnt] = tmp;
70         }
71     }
72 }
73 
74 void solve2() { // 有向图
75     int n = read(), m = read(), s = 0;
76     for (int i=1; i<=m; ++i) {
77         int u = read(), v = read();
78         add_edge(u, v);
79         deg[v] --; deg[u] ++; s = u;
80     }
81     for (int i=1; i<=n; ++i) // 出度等于入度
82         if (deg[i]) { puts("NO"); return ; }
83     dfs2(s);
84     if (cnt < m) puts("NO");
85     else { puts("YES"); for (int i=cnt; i>=1; --i) printf("%d ", ans[i]); }
86 }
87 
88 int main() {
89     int T = read();
90     if (T == 1) solve1();
91     else solve2();    
92     return 0;
93 }