欧拉回路（dfs变形+优化）

大家好，欢迎来到IT知识分享网。

定义：
欧拉路径：通过图中每条边恰好一次的路径
欧拉回路：通过图中每条边恰好一次的回路

对无向图（边连通）：
    若起点与终点不同：则起点与终点度数为奇数，其它点度数为偶数
    若起点与终点相同：则不存在某点的度数为奇数
    存在欧拉路劲的充分必要条件：存在0或2个点的度数为奇数
    存在欧拉回路的充分必要条件：不存在度数为奇数的点

对有向图（边连通）：
    若起点与终点不同：则起点的出度比入度多1，终点入度比出度多1，其它点的出度与入度相同
    若起点与终点相同：则所有点的出度与入度相同
    存在欧拉路径的充分必要条件：所有点出度与入度相同，或者仅存在一个出度比入度多1的点（起点）和一个点入度比出度多1的点（终点），其它点出度与入度相同
    存在欧拉回路的充分必要条件：所有点的出度与入度相同

求欧拉路径/欧拉回路(需保证边连通)：
利用dfs求欧拉路径/回路：在遍历完当前节点的所有邻接点后，将该点加入到序列中，在做完dfs后，欧拉回路为序列的逆序。

dfs求欧拉路径模拟：

如上图所示，图中含多个顶点，其中只标出A，B，C方便算法描述。
在进行dfs遍历时:
路径1：从A点出发，遍历到B；
路径2：从B点出发，遍历到C；
路径4：回溯到B，依次添加节点到序列中，添加的节点顺序即为路径4；
路径3：从B点出发，访问第2条边，直到遍历到自身；
路径5：回溯到B，依次添加节点到序列中，添加的节点顺序即为路径5；
路径6：回溯到A，依次添加节点到序列中，添加的节点顺序即为路径6；
若我们在遍历每个节点时将其添加到序列中，得到的序列为路径1，路径2，路径3，显然不是欧拉路径；而我们在遍历完每个节点的所有邻接点后将其添加进序列，得到的序列为路径4，路径5，路径6，将序列逆置之后，得到路径1，路径3，路径2，即欧拉路径。

dfs删边优化：因为欧拉路径中每条边只走一次，因此我们可以在每条边被遍历之后把它删除，以节省判重时间，达到时间上的优化。

void dfs(int u) { for (int i = h[u]; i != -1; i = h[u]) { ...... h[u] = ne[i];//删边操作 dfs(e[i]); ...... } }

dfs删边优化模拟：
假设节点u存在5个自环，对应编号为1~5
在dfs遍历到第一层，令h[u] = ne[i] = 2；遍历到第2层时，令h[u] = ne[i] = 3；遍历到第3层时，令h[u] = ne[i] = 4；直到第五层，令h[u] = -1；开始回溯。
回溯到第4层，i=h[u]=-1；回溯
回溯到第3层，i=h[u]=-1；回溯
回溯到第2层，i=h[u]=-1；回溯
回溯到第1层，i=h[u]=-1；结束 
因此每条边都被遍历过，而时间也是线性的。

Description

给定一张图，请你找出欧拉回路，即在图中找一个环使得每条边都在环上出现恰好一次。

Input

第一行包含一个整数 t，t ∈ {1, 2}，如果 t = 1，表示所给图为无向图，如果 t = 2，表示所给图为有向图。 

第二行包含两个整数 n, m ( 1 ≤ n ≤ 105 ,  0 ≤ m ≤ 2×105 ) ，表示图的节点数和边数。 

接下来 m 行中，第 i 行两个整数 vi, ui，表示第 i 条边（从 1 开始编号）。

• 如果 t = 1 则表示 vi 到 ui 有一条无向边
• 如果 t = 2 则表示 vi 到 ui 有一条有向边

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

点的编号从 1 到 n 。

Output

如果无法一笔画出欧拉回路，则输出一行：NO 。

否则，输出一行：YES ，接下来一行输出 任意一组 合法方案即可。

• 如果 t = 1，输出 m 个整数 p1, p2, …, pm 。令 e = | pi |，那么 e 表示经过的第 i 条边的编号。如果 pi 为正数表示从 ve 走到 ue，否则表示从 ue 走到 ve 。
• 如果 t = 2，输出 m 个整数 p1, p2, …, pm 。其中 pi 表示经过的第 i 条边的编号。

Sample Input

Sample Output

全部代码如下：

#include<bits/stdc++.h> using namespace std; #define N  #define M  #define INF 0x3f3f3f3f int n, m, type, cnt, ans[M]; bool used[2 * M]; int in[N], out[N]; int h[N], e[2 * M], ne[2 * M], idx; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx++; } void dfs(int u) { for (int i = h[u]; i != -1; i = h[u]) { if (used[i]) { h[u] = ne[i]; continue; } used[i] = true; if (type == 1)used[i^1] = true;//若为无向图，则将反向边判重 h[u] = ne[i]; dfs(e[i]); if (type == 1) { if (i % 2)ans[++cnt] = -(i + 1) / 2; else ans[++cnt] = (i + 2) / 2; } else ans[++cnt] = i + 1; } } int main() { memset(h, -1, sizeof h); scanf("%d", &type); scanf("%d%d", &n, &m); for (int i = 0; i < m; i++) { int a, b; scanf("%d%d", &a, &b); add(a, b); in[b]++, out[a]++; if (type == 1) add(b, a); } if (type == 1) {//无向图需保证每个点的度为偶数 for (int i = 1; i <= n; i++) { if ((in[i] + out[i]) % 2) { printf("NO\n"); return 0; } } } else {//有向图需保证每个点的出度与入度相等 for (int i = 1; i <= n; i++) { if (in[i] != out[i]) { printf("NO\n"); return 0; } } } //防止在单独孤立的点上求bfs for (int i = 1; i <= n; i++) if (h[i] != -1) { dfs(i); break; } //判断边是否连通 if (cnt != m) { printf("NO\n"); return 0; } printf("YES\n"); //逆序输出序列 for (int i = cnt; i; i--) printf("%d ", ans[i]); return 0; }