C++ 并查集解决亲戚关系判定问题

题目描述

给定一个家族人员关系图，判断任意给出的两个人是否具有亲戚关系。

规定：

• x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚。
• 如果 x，y 是亲戚，那么 x 的亲戚都是 y 的亲戚，y 的亲戚也都是 x 的亲戚。

输入格式

第一行：三个整数 n,m,p，（n,m,p ≤ 5000），分别表示有 n 个人，m 个亲戚关系，询问 p 对亲戚关系。

以下 m 行：每行两个数 M_i，M_j，1 ≤ M_i,~M_j≤ N，表示 M_i 和 M_j 具有亲戚关系。

接下来 p 行：每行两个数 P_i,P_j，询问 P_i 和 P_j 是否具有亲戚关系。

输出格式

p 行，每行一个 Yes 或 No。表示第 i 个询问的答案为“具有”或“不具有”亲戚关系。

示例

样例输入

6 5 3
1 2
1 5
3 4
5 2
1 3
1 4
2 3
5 6

样例输出

Yes
Yes
No

C++ 代码

#include <iostream>
#include <vector>

using namespace std;

// 并查集的数据结构
class UnionFind {
public:
    vector<int> parent;

    UnionFind(int n) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
    }

    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    void unite(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
        }
    }
};

int main() {
    int n, m, p;
    cin >> n >> m >> p;

    UnionFind uf(n);

    for (int i = 0; i < m; i++) {
        int Mi, Mj;
        cin >> Mi >> Mj;
        uf.unite(Mi - 1, Mj - 1);
    }

    for (int i = 0; i < p; i++) {
        int Pi, Pj;
        cin >> Pi >> Pj;
        if (uf.find(Pi - 1) == uf.find(Pj - 1)) {
            cout << "Yes" << endl;
        } else {
            cout << "No" << endl;
        }
    }

    return 0;
}

代码解析

1. 并查集数据结构: 使用 UnionFind 类来实现并查集，它包含一个 parent 数组，记录每个节点的父节点。
2. find(x) 函数: 寻找节点 x 的根节点，并进行路径压缩优化，将路径上的所有节点的父节点指向根节点，以提高效率。
3. unite(x, y) 函数: 合并节点 x 和 y 所属的集合，将 x 的根节点的父节点指向 y 的根节点。
4. 主函数: 首先读取输入数据，包括人数 n，亲戚关系数量 m 和询问次数 p。
   • 初始化一个大小为 n 的并查集 uf。
   • 读取 m 个亲戚关系，并使用 unite 函数将他们合并到同一个集合中。
   • 读取 p 个询问，并使用 find 函数判断两个人的根节点是否相同，从而判定他们是否具有亲戚关系。

总结

并查集是一种简单高效的算法，在解决类似亲戚关系判定这类问题时非常有用。通过学习并查集的原理和代码实现，我们可以更好地理解数据结构和算法的应用。