当前位置：首页 > article >正文

数据结构与算法图论并查集

article 2024/9/20 13:34:03

前言

写一道并查集的题

判断是否为亲戚

原题目：现在有若干家族图谱关系，给出了一些亲戚关系，如Marrv和Tom是亲戚，Tom和Ben是亲戚等等。从这些信息中，你可以推导出Marry和Ben是亲戚。请写一个程序，对于我们的关于亲戚关系的提问，以最快速度给出答案。

【输入格式】

第一部分是以N.M开始。N为人数(1<=N<=20000).这些人的编号为1.2.3…N。下面有M行(1<=M<=1000000),每行有两个数a.b.表示a和b是亲戚。
第二部分是以Q开始。以下Q行有Q个询问(1<=Q<=1000000)，每行为c，d，表示询问c和d是否为亲戚。

【输出格式】

对于询问c，d，输出一行：若c，d为亲戚，则输出"YES"，否则输出“NO”。【输入样例】
10 7
2 4
5 7
1 3
8 9
1 2
5 6
2 3
3
3 4
7 10
8 9
【输出样例】
YES
NO
YES

分析

我们可以使用并查集的思想，我们首先初始化将每个元素的父节点初始化为自己，将有关系的两个元素进行合并，然后判断是否有关系我们只需要查看元素a和元素b的祖先是否为同一个即可，如果是则是亲戚关系

并查集

并查集（Union-Find Set）是一种数据结构，用于处理一些不交集的合并及查询问题。

它主要支持两个操作：
查找（Find）：确定某个元素属于哪个集合。这个操作通常涉及到路径压缩，以提高效率。
合并（Union）：将两个集合合并成一个集合。为了保持结构的平衡，通常使用按秩合并或按大小合并的方法。
并查集的应用场景包括：
网络连接：确定两个节点是否在同一网络中。
图的连通性：检查图中的不同连通组件。
集合划分：在动态连接的场景中处理不同的集合划分。
在这里插入图片描述

代码如下：

#include <bits/stdc++.h>
#define int long long
#define PII pair<int,int>
#define endl '\n'
#define LL __int128
const int N = 2e5 + 10; // 最大节点数
const int M = 1e3 + 10; // 最大边数（在本代码中不直接使用）
int a[N], p[N]; // p 数组用于存储并查集的父节点

using namespace std; 

// 查找操作，使用路径压缩
int find(int x) {
    if (p[x] != x) {
        // 如果 p[x] 不是 x 本身，则递归查找父节点，并进行路径压缩
        return p[x] = find(p[x]);
    }
    return p[x]; // 返回根节点
}

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, m, x, y, q;
    cin >> n >> m; // 读入节点数 n 和边数 m

    // 初始化并查集，每个节点的父节点初始化为自身
    for (int i = 1; i <= n; ++i) {
        p[i] = i;
    }

    // 处理 m 条边
    for (int i = 1; i <= m; i++) {
        cin >> x >> y; // 读入边 (x, y)
        // 合并操作：将 x 和 y 所在的集合合并
        // 将 x 的根节点的父节点设置为 y 的根节点
        p[find(x)] = find(y);
    }

    cin >> q; // 读入查询数 q

    // 处理 q 条查询
    for (int i = 1; i <= q; i++) {
        cin >> x >> y; // 读入查询对 (x, y)
        // 查询 x 和 y 是否在同一个集合中
        if (find(x) == find(y)) {
            cout << "YES" << endl; // 如果 x 和 y 在同一个集合中，输出 YES
        } else {
            cout << "NO" << endl; // 否则，输出 NO
        }
    }

    return 0;
}