本文共 1461 字，大约阅读时间需要 4 分钟。

并查集是一种高效的数据结构，用于管理动态集合的合并和查找操作。它的核心思想是通过路径压缩和按秩合并，确保查找和合并操作的时间复杂度接近常数。这正是解决这个问题的关键，因为我们需要快速判断两个节点是否属于同一个亲戚集合。

并查集的实现

我们使用并查集来维护每个节点的亲戚关系。具体步骤如下：

代码实现

#include 
   
    #include 
    
     using namespace std;int n, m, p;int pre[5005]; // 节点编号从1到nint find(int x) {    if (pre[x] == 0) return x;    pre[x] = find(pre[x]); // 路径压缩    return pre[x];}void bcj(int x, int y) {    int x_root = find(x);    int y_root = find(y);    if (x_root != y_root) {        pre[y_root] = x_root; // 按秩合并，合并到较小的树上    }}int main() {    cin >> n >> m >> p;    for (int i = 1; i <= m; ++i) {        int x, y;        cin >> x >> y;        bcj(x, y);    }    for (int i = 1; i <= p; ++i) {        int x, y;        cin >> x >> y;        if (find(x) == find(y)) {            cout << "Yes";        } else {            cout << "No";        }    }}
    
   

解释

样例测试

输入：

6 5 31 21 53 45 21 31 42 35 6

输出：

YesYesNo

结果解释

• 查询1-3：1和3都在同一个集合中，输出Yes。
• 查询1-4：1和4都在同一个集合中，输出Yes。
• 查询2-3：2和3都在同一个集合中，输出Yes。
• 查询5-6：5和6不在同一个集合中，输出No。

通过这样的步骤，我们可以高效地判断任意两个节点是否是亲戚。并查集的高效操作使得即使在大规模数据下，问题也能快速解决。