To boldly go where no one has gone before.

【学习笔记】欧拉回路

2019-03-25 13:05:19


欧拉回路是指:在一个连通图$G$中,若存在一条回路使得$G$中的每条边都被且仅被经过一次,这条回路就叫欧拉回路,这个图就是欧拉图。

另外,在一个连通图$G$中,若存在一条路径使得$G$中的每条边都被且仅被经过一次,这条路径就叫欧拉通路,这个图就是半欧拉图

很显然,如果统计所有点的度数$deg[i]$,对于一个欧拉图,不存在一个点$u$的入度$deg[u]$为奇数;对于一个半欧拉图,有且仅有两个点$u,v$的度数$deg[u],deg[v]$为奇数,且该图中的欧拉通路以$u,v$为端点。

$\textbf{Hierholzer}$算法

$Hierholzer$算法是指:在一个欧拉图$G$中,随机选取一个点作为起始点,每次遍历点$u$所连接的点$v$,对于点$v$,先删去无向边$<u,v>$,然后对点$v$跑$\text{dfs}$。循环结束后,将$u$倒序记录在$res[i]$数组中。算法结束后,$res[i]$中的路径就是一条欧拉回路。

下面是用邻接矩阵存图后的$Hierholzer$算法实现。

inline void dfs(int i) {
    for(register int j = 1; j <= MAXN; j++) {
        if(G[i][j]) {
            G[i][j] = G[j][i] = 0;
            dfs(j);
        }
    }
    res[tail--] = i;
}

例题 P1341

思路: 给出的字母对实际上就是在构造边,存完边之后直接跑$Hizerholzer$即可。由于要保证字典序最小,所以只需要注意在遍历的时候按照字典序从小到大遍历就可以了。

//code
#include<bits/stdc++.h>
using namespace std;
const int MAXN = (int)'z' + 10;

int G[MAXN][MAXN];
int deg[MAXN];
char res[MAXN * MAXN];
int n, tail;

inline void dfs(int i) {
    for(register int j = 'A'; j <= 'z'; j++) {
        if(G[i][j]) {
            G[i][j] = G[j][i] = 0;
            dfs(j);
        }
    }
    res[tail--] = (char)i;
}

int main() {
    scanf("%d", &n);
    tail = n;
    for(register int i = 1; i <= n; i++) {
        char s[10];
        scanf("%s", s);
        G[s[0]][s[1]] = G[s[1]][s[0]] = 1;
        deg[s[0]]++, deg[s[1]]++;
    }
    char begin = 0;
    int cnt = 0;
    for(register int i = 'A'; i <= 'z'; i++) {
        if(deg[i] % 2) {
            cnt++;
            if(!begin)
                begin = (char)i;
        }
    }
    if(cnt && cnt != 2) {
        printf("No Solution");
        return 0;
    }
    if(!begin)
        for(register int i = 'A'; i <= 'z'; i++)
            if(deg[i]) {
                begin = (char)i;
                break;
            }
    dfs(begin);
    puts(res);
    return 0;
}