亲戚|题解

前言：

这是一道并查集模板题。

思路：

注意到本题$n,m,p$数据较小，对于每次询问可以暴力的跑 $dfs$ ,用此方法可以通过此题，但是速度较慢，所以可以使用并查集。

哦，但并查集是啥？

当希望知道某个数据是否存在一个集合中，或者两个元素是否在同一个集合中时，就需要使用一些集合数据结构来维护集合元素之间的关系，而并查集就是其中的一种。

这道题的关键是判断两个人是否在一个“家族”里，但怎么判断呢？可以在家中选出一名“族长”来代表一个家族，所以只要判断两人的“族长”是否相同即可。

最开始每个人都“自成一族”，每个人都是“族长”。在得知亲戚关系时，可以将两个人所在的家族合并，变成一个家族。

以上大概就是并查集的思路了。

那查找的代码如何实现呢？

int find(int x){
	if(x==fa[x]) return x;//如果当前节点是根节点，也就是找到家族的“族长”，就返回“族长”编号
	return fa[x]=find(fa[x]);//没找到就继续往上找，这里使用路径压缩，效率翻倍
} 

会查找了，如何合并呢？

void make(int c1,int c2){
	int f1=find(c1),f2=find(c2);//找到两个人的“族长”
	if(f1!=f2) fa[f1]=f2;//若本生不是一个家族，那就并到一个家族，选一个旧“族长”当新“族长”
}

时间复杂度：

$O(N+M+P)$
注意：查找要使用路径压缩，应为速度较快，时间复杂度$O(α(n))$，可以认为是常数。

代码：

已详细讲解并查集，且合并和查找都给出代码，其他自己思考完成。

备注：

本文讲解参考了部分$深入浅出（基础篇）$的内容，希望通过这篇题解对你有所帮助。