欧拉道路/回路总结

充要条件

   如果一个无向图是连通的，且只有两个奇点或者无奇点，则一定存在欧拉道路。
   如果有两个奇点，则必须从其中一个奇点出发，另一个奇点终止；如果奇点不存在，则可以从任意点出发，最终一定会回到该点（称为欧拉回路）。

后序遍历dfs求解欧拉道路

   求欧拉道路的模板

void euler(int u){
	for(int v = 0; v < n; v++) if(G[u][v] && !vis[u][v]) {
		vis[u][v] = vis[v][u] = 1;
		euler(v);
		printf("%d %d\n", u, v);
	}
}
1
2
3
4
5
6
7

   欧拉道路可能包含回路，那么在dfs时，可能提前找到回路，这条回路可能不是完整的欧拉道路（因为没有遍历完所有的边！）如果写成前序遍历的话，存储起来的路径就不是一条完整的路径了！它有可能是多条回路组成的！答案就是错误的！如果是后序遍历的话，当dfs时遇到了回路，那么就退出当前栈的搜索并继续寻找其他的路径，最终得到只有一条回路的路径——欧拉回路。

例子

   UVA-10054 The Necklace
   有一种由彩色珠子连接成的项链。每个珠子的两半由不同颜色组成。如下图所示，相邻两个珠子在接触的地方颜色相同。现在有一些零碎的珠子，需要确认它们是否可以复原成完整的项链。

   先给出AC代码

#include 
#include 
using namespace std;

#define N 61
#define M 1010
int u[M], v[M], g[N][M], path[M<<1], cnt[N], c[N], cc, m; bool vis[M];

bool check() {
    for (int i=1; i<N; ++i) if (cnt[i]&1) return false;
    return true;
}

void euler(int u) {
    for (int i=0, j; i<cnt[u]; ++i) if (!vis[j = g[u][i]]) {
        int v = ::u[j]+::v[j]-u;
        vis[j] = true; euler(v);
        path[cc++] = v; path[cc++] = u;
        while (c[u]>0) path[cc++] = u, path[cc++] = u, --c[u];
    }
}

void solve() {
    if (check()) {
        memset(vis, cc = 0, sizeof(vis)); euler(u[0]);
        if (cc == 2*m) {
            for (int i=cc-1; i>0; i-=2) cout << path[i] << ' ' << path[i-1] << endl;
            return;
        }
    }
    cout << "some beads may be lost" << endl;
}

int main() {
    int T; cin >> T;
    for (int kase=1; kase<=T; ++kase) {
        cin >> m; memset(cnt, 0, sizeof(cnt)); memset(c, 0, sizeof(c));
        for (int i=0; i<m; ++i) {
            cin >> u[i] >> v[i];
            u[i] != v[i] ? g[u[i]][cnt[u[i]]++] = g[v[i]][cnt[v[i]]++] = i : ++c[u[i]];
        }
        if (kase>1) cout << endl;
        cout << "Case #" << kase << endl;
        solve();
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

   对这里的euler方法及输出部分详细展开一下：

void euler(int u) {
    for (int i=0, j; i<cnt[u]; ++i) if (!vis[j = g[u][i]]) {
        int v = ::u[j]+::v[j]-u;
        vis[j] = true; euler(v);
        path[cc++] = v; path[cc++] = u;
        while (c[u]>0) path[cc++] = u, path[cc++] = u, --c[u];
    }
}
void solve() {
    if (check()) {
        memset(vis, cc = 0, sizeof(vis)); euler(u[0]);
        if (cc == 2*m) {
            for (int i=cc-1; i>0; i-=2) cout << path[i] << ' ' << path[i-1] << endl;
            return;
        }
    }
    cout << "some beads may be lost" << endl;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

   由于是后续遍历，存的路径其实是逆序的，输出时需要注意（当然本题顺序输出逆序输出都可以）。
   并且euler方法深搜结束后路径长度如果不等于所有点数（含重复点），说明不止一个连通分量。可见对于一定要求出欧拉路径的问题，可以不必先检查连通分量数是否唯一，在dfs结束时判断路径是否包含所有点（含重复点）即可。