虚虚实实 题解

题目描述

给定一个无向图，判断是否存在一条路径能够：

• 经过所有边恰好一次
• 经过所有点
• 不要求回到起点

即判断图中是否存在欧拉路径（Eulerian Path）。

核心结论

答案： 当且仅当图连通且奇度数顶点个数为 0 或 2 时，存在欧拉路径。

• 奇度数顶点个数为 0：存在欧拉回路
• 奇度数顶点个数为 2：存在欧拉路径（从奇度数顶点开始和结束）

标程实现

#include <bits/stdc++.h>
using namespace std;

int de[33], fa[33];

int f(int x) {
    return fa[x] == x ? x : fa[x] = f(fa[x]);
}

int main() {
    int _;
    cin >> _;
    while (_--) {
        int n, m, i, x, y;
        cin >> n >> m;
        
        // 初始化
        for (i = 1; i <= n; i++) {
            fa[i] = i;
            de[i] = 0;
        }
        
        // 读入边并维护度数和连通性
        for (i = 0; i < m; i++) {
            cin >> x >> y;
            de[x]++;
            de[y]++;
            fa[f(x)] = f(y);  // 并查集合并
        }
        
        // 检查连通性和奇度数顶点个数
        int cnt = 0, jud = 1;
        for (i = 1; i <= n; i++) {
            if (f(i) != f(1)) jud = 0;  // 检查连通性
            cnt += de[i] & 1;           // 统计奇度数顶点
        }
        
        if (!jud || cnt > 2) cout << "Xun\n";
        else cout << "Zhen\n";
    }
}

算法解释

欧拉路径判定条件

对于无向图，存在欧拉路径的充要条件是：

1. 图连通
2. 奇度数顶点个数为 0 或 2

算法步骤

1. 初始化：

   • 使用并查集维护连通性
   • 度数数组记录每个顶点的度数

2. 读入边：

   • 更新两个端点的度数
   • 使用并查集合并两个顶点

3. 检查条件：

   • 连通性：检查所有顶点是否与顶点1在同一连通分量
   • 度数条件：统计奇度数顶点个数

关键技巧

• de[i] & 1：快速判断度数是否为奇数
• 并查集路径压缩：fa[x] = f(fa[x])
• 只需检查与顶点1的连通性，因为连通分量内部任意两点连通

并查集学习资源

如果对并查集算法不熟悉，推荐观看这个1分钟快速入门视频： 《1分钟学会并查集》

示例分析

示例1：

• 图连通，奇度数顶点个数为2（顶点1和顶点3）
• 存在欧拉路径：1→2→3→1→4→3

示例2：

• 图不连通
• 不存在欧拉路径

复杂度分析

• 时间复杂度： ，其中 是阿克曼函数的反函数
• 空间复杂度：