《洛谷深入浅出基础篇》P1551亲戚——集合——并查集P1551亲戚

上链接：P1551 亲戚 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1551

上题干： 

题目背景

若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。

题目描述

规定：x 和 y 是亲戚，y 和 z 是亲戚，那么 x 和 z 也是亲戚。如果x，y 是亲戚，那么 �x 的亲戚都是 y 的亲戚，y 的亲戚也都是 x 的亲戚。

输入格式

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

以下 m 行：每行两个数 Mi​，Mj​，1≤Mi​, Mj​≤n，表示 Mi​ 和 Mj​ 具有亲戚关系。

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

输出格式

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

输入输出样例

输入 #1复制

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

输出 #1复制

Yes
Yes
No

 我们拿样例来模拟一下：

由于题目说了，如果x，y是亲戚，那么x的亲戚就是y的亲戚，y的亲戚就是x的亲戚

所以我们把互相为亲戚的人放入一个集合中

当我们需要查询任意两个人是否为亲戚关系的时候，我们就可以查询这两个人是否在同一个集合中

那么如何判断这两个人是否在一个集合之中呢？

我们给这个集合创造一个特性，并且集合里面的人都满足这个特性，所以我们只需要判断要查询的人是否满足这种特性，就可以知道他们是不是在同一个集合里面。

这个特性就是祖先关系。

当一群人的祖先是同一个人的时候，这群人互相是亲戚。

首先，并查集的初始化：

将每个人初始化为自己家族的祖先：（我是我爹）

fa[i]=i;、

合并：

然后我们会循环输入亲戚关系

比如样例中的，先输入 1   2 ， 代表这两个人是亲戚

所以我们需要将 1 ， 2 的家族合并，使得他们的祖先为同一个人，可以为1，也可以为2.

fa[fa[1]]=fa[2];

代表将家族1的祖先 并入家族2中当族人

第二次输入  1  5  

我们操作的目的是：代表将家族1的祖先 并入家族5中当族人

而家族1的祖先是2，说明2是家族5中的族人，说明，1，2被并入5了。

即：

fa[fa[1]] = fa[5]

第三次输入  3  4

同理，将家族3的祖先并入家族4中当族人

fa[fa[3]]=fa[4]

第四次输入  5 2

我们发现家族5的祖先是5，家族2的祖先是2，所以不需要合并

第五次输入：1，3

将家族1的祖先并入家族3

fa[fa[1]]=fa[3]

即将5并入家族3当族人

那么模拟完了之后，我们可以得到如下的关系

进行完这些操作之后，我们创建完了一个并查集，就可以查询元素是否属于某个集合了。

上代码：

const int N = 5e3 + 10;
int fa[N];
int find1(int x)
{
	if (fa[x]==x)return fa[x]; //如果家族x的祖先是x，返回祖先
	else return fa[x] = find1(fa[x]);//如果不是，查找 （家族x的祖先）（假设是家族y）是不是其家族（家族y）的祖先
}//不断递归，最终返回的是 x 的祖先
void join1(int c1, int c2)
{
	int f1 = find1(c1), f2 = find1(c2);//找到c1，c2的祖先f1，f2
	if (f1 != f2)fa[f1] = f2;//如果不是同一个人，那么将家族f1并入家族f2
}
int main()
{
	int n, m, p;
	cin >> n >> m >> p;
	for (int i = 1; i <= n; i++)fa[i] = i;//初始化父节点
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		cin >> x >> y;
		join1(x, y);
	}
	for (int i = 1; i <= p; i++)
	{
		int x, y;
		cin >> x >> y;
		find1(x) == find1(y) ? cout << "Yes" << endl : cout << "No"<
	}
}