数据结构与算法图论 并查集
前言
写一道并查集的题
判断是否为亲戚
原题目：现在有若干家族图谱关系，给出了一些亲戚关系，如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;
}