欧拉路

欧拉路

概念

经过图中所有边恰好一次的通路称为欧拉通路或欧拉路

经过图中所有边恰好一次的回路称为欧拉回路

性质

无向图

对于无向图G，G中存在欧拉回路当且仅当G中所有度非0的点是连通的且没有奇数度数的点。

对于无向图G，G中存在欧拉路当且仅当G中所有度非0的点是连通的且G中恰有0或2个奇数度数的点(0个表示存在欧拉回路)。

有向图

对于有向图G，G中存在欧拉回路当且仅当G中所有度非0的点是强连通的且每个点的入度和出度相同。

对于有向图G，G中存在欧拉路当且仅当：

• 将G中所有有向边改为无向边后，G中所有度非0的点是连通的；

• 最多只有一个点的出度减去入度为1；

• 最多只有一个点的入度减去出度为1；

• 其他所有点的入度等于出度。

时间复杂度$O(n+m)$

求有向图欧拉通、回路：

VI edge[N + 1];
int n, m, l, f[N + 1], ind[N + 1], outd[N + 1], c[M + 2], v[N + 1];//ind[x],outd[x]表示出度和入度，c记录欧拉路，f[x]表示edge[x]的遍历情况
inline void dfs(int x) {
    while (f[x] < v[x]) {//v[x]即edge[x].size()
        int y = edge[x][f[x]];
        f[x]++;
        dfs(y);
        c[++l] = y;
    }
}
inline void Euler() {
    int x = 0, y = 0, z = 0;
    for (int i = 1; i <= n; i++) {//判断是否有欧拉路
        if (ind[i] + 1 == outd[i])
            x = i, ++y;
        if (ind[i] != outd[i])
            ++z;
    }
    if (!((y == 1 && z == 2) || !z)) {
        printf("No\n");
        return;
    }
    if (!x)
        for (int i = 1; i <= n; i++)
            if (ind[i]) x = i;
    memset(f, 0, sizeof(f));
    l = 0;
    dfs(x);
    c[++l] = x;
    if (l != m + 1) {//判断是否连通
        printf("No\n");
        return;
    }
    printf("Yes\n");
    for (int i = l; i; --i)
        printf("%d", c[i]);
}
void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        edge[x].push_back(y);
        ++outd[x], ++ind[y];
    }
    for (int i = 1; i <= n; i++) {
        v[i] = edge[i].size();
        //若要输出字典序最小的欧拉路，则要排序
        //sort(edge[i].begin(), edge[i].end());
    }
    Euler();
}

求无向图欧拉通、回路

struct Node {
    int y, idx;
    Node(int _y, int _idx) { y = _y, idx = _idx; }
    bool operator<(const Node& A) const {
        return y < A.y;
    }
};
vector<Node> edge[N + 1];
int n, m, l, cnt=1,f[N + 1], d[N + 1], c[M + 2], v[N + 1];//d[x]表示度数，c记录欧拉路，f[x]表示edge[x]的遍历情况,cnt记录边的编号
bool b[2 * M + 2];//判断这条边是否走过，走过为true
inline void dfs(int x) {
    while (f[x] < v[x]) {//v[x]即edge[x].size()
        int y = edge[x][f[x]].y, idx = edge[x][f[x]].idx;
        if (!b[idx]) {
            f[x]++;
            b[idx] = b[idx ^ 1] = true;
            dfs(y);
            c[++l] = y;
        }
        else f[x]++;
    }
}
inline void Euler() {
    int x = 0, y = 0;
    for (int i = 1; i <= n; i++) {//判断是否有欧拉路
        if (d[i] & 1) x = i, ++y;
    }
    if (y && y != 2) {
        printf("No\n");
        return;
    }
    if (!x)
        for (int i = 1; i <= n; i++)
            if (d[i]){
                x = i;
                break;
            }
    memset(f, 0, sizeof(f));
    memset(b, false, sizeof(b));
    l = 0;
    dfs(x);
    c[++l] = x;
    if (l != m + 1) {//判断是否连通
        printf("No\n");
        return;
    }
    printf("Yes\n");
    for (int i = l; i; --i)
        printf("%d", c[i]);
}
void solve() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++) {
        int x, y;
        scanf("%d%d", &x, &y);
        edge[x].push_back({ y,++cnt });
        edge[y].push_back({ x,++cnt });
        ++d[x], ++d[y];
    }
    for (int i = 1; i <= n; i++) {
        v[i] = edge[i].size();
        //若要输出字典序最小的欧拉路，则要排序
        //sort(edge[i].begin(), edge[i].end());
    }
    Euler();
}