并查集
并查集就是一种维护集合的数据结构，可以完成不相交集合上的合并、查询。
算法逻辑
用一个非常经典的例子 —— 帮派问题来解释下并查集。
一个帮派肯定有一个帮主（根节点），这个帮主就代表这个帮派。（这就是并查集的核心思想之一 —— 用集合中的一个元素来代表集合。）每个人都有一名负责人（父节点）。开始的时候每个人都是一个帮派，相互独立。换句话说每个人的帮主就是自己，负责人也是自己。N 个人就有 N 个帮派。我们维护一个
s[i]数组，来表示点i的负责人（注意不是点i的帮主）。那刚开始的时候，s[i] = i。下图中箭头的指向就是该人的负责人。点 1 跟点 2 打架赢了，那么点 2 就认点 1 当老大，点 2 所在的帮派就变成了点 1 所在的帮派。这就是并查集的合并操作。如何合并呢，具体操作就是点 2 的负责人
s[2]改成点 1，s[2] = 1，帮主是点 1。（怎么知道帮主是点 1 的，因为点 2 的负责人是点 1，点 1 的负责人是自己，所以点 1 是帮主。）点 2 要跟点 3 打架，他不知道能不能打，万一是一个帮派的，不就误伤了。所以他要看点 3 跟自己是不是一个帮派。这就是并查集的查询操作。
s[3] = 3说明点 3 负责人是自己，进而点 3 的帮主就是 3，而点 2 的帮主是 1，所以不是一个帮派，可以打。点 2 打输了，点 2 所在的帮派要合并到点 3。（太坑了，小弟打架打输了，大哥帮派归对方了。）s[2] = 3。诶大家肯定发现问题了，这样的话，1 的负责人还是 1 呀，他还是自成一个帮派呀，所以不能这么改，我们应该改s[1] = 3。也就是哪方打输了，哪方的帮主就要把认对方当负责人。点 4 要跟点 1 打架，还是看看是不是一个帮派的，发现不是，可以打架。最后点 4 打输了，点 4 的帮派要合并到点 1 所在帮派，`s [4] = 1
通过上述流程，得到的最终结果为
s[1] = 3、s[2] = 1、s[3] = 3、s[4] = 1。
至此，我们已经讲完了并查集的基本操作（合并，查询）、核心思想（用集合中的某个元素代表集合本身）。接下来我们用代码来具体实现上述的逻辑。
初始化
int s[N];//开一个数组来维护某个点的负责人
for(int i = 1; i <= n; i++) s[i] = i;//点i的负责人是i。查询（找到某个人的帮派）
查询某个点所在的帮派，也就是找到帮主。因为算法逻辑第一句话就告诉了大家：一个帮派肯定有一个帮主，这个帮主就代表这个帮派。
递归写法：
int find（int x）//找到x的帮主
{
if (x == s(x)) return x;//x的负责人是x，说明x就是帮主
return find(s[x]);//x的负责人是y，找y的负责人，一直递归，直到负责人是本身（说明找到帮主了）。
}非递归写法：
int find(int x)
{
while(x != s(x)) x = s(x);//获得x的负责人，直到负责人是自己。
return x;
}合并（合并两个帮派）
void join(int x,int y)
{
int a = find(x), b = find(y);//x跟y打架输了，找到x的帮主跟y的帮主，让x的帮主认y的帮主当负责人。
s[a] = b;//也可以加个判断条件if (a != b) s[a] = b;
}思考：可以这样写吗： s[a] = y ；也就是开头帮派例子第四步描述的逻辑，让 x 的帮主 a 认 y 当负责人，而不是 y 的帮主。这种写法会增加树的深度，进而降低查询的效率。我在洛谷提交了这种写法，TLE 了。
所以为了提高代码效率，找到 x 和 y 的帮主，让一个人的帮主当另一个人的帮主的负责人即可。
帮派问题有些复杂了，通过上述具体的代码实现，我们可以发现实际的并查集算法逻辑并不需要关注哪两个人打架了，哪个帮派打赢了，只要知道哪两个帮派打架（合并）了，这两个帮派变成了一个帮派即可。这里体现的就是并查集的另一个核心特点 —— 无向性。
回过头来，总结下并查集最核心的思想：对同一个集合来说只存在一个根节点，且将其作为所属集合的标识。
路径优化
在做并查集题目时，一定会用到路径压缩这个优化技术。
思考查询操作代码的流程：
int find（int x）//找到x的帮主
{
if (x == s(x)) return x;//x的负责人是x，说明x就是帮主
return find(s[x]);//x的负责人是y，找y的负责人，一直递归，直到负责人是本身（说明找到帮主了）。
}查找 2 的帮主 find(2) ， 2 的负责人是 1 ，返回 find(1) ， 1 的负责人是 3 ，返回 find(3) ， 3 的负责人是自己，返回 3 ，所以 find(1) = 3 ， find(2) = 3 。成功找到 2 的帮主。既然已经知道 2 的帮主是 3 ，那么我们是不是可以将 2 的负责人改成 3 呢，这样下次再查找的时候就不用这么麻烦了，直接一步到位。
注
这个思想就是路径优化。代码即 return s[x] = find(s[x]) ，这里的代码看起来复杂，实际上只涉及到一个赋值的操作，将 x 的负责人改成帮主。
仅进行路径压缩使查询的时间复杂度降低至 $O (logn)$，还有一种优化方式叫做按秩合并优化，可以将查询复杂度降低至接近常数。先留个坑，以后遇到再补充。
按秩合并优化
2 和 5 进行合并，也就是 2 的帮主 3 跟 5 的帮主 4 合并。谁当谁的负责人呢？此时我们选择高度大的作为负责人，也就是 4 当 3 的负责人，这样可以使合并之后的高度不变。
额外维护一 h 数组，表示以 x 为根的子树的高度。
void join(int x, int y)
{
int a = find(x), b = find(y);
if(a == b) return;
if(h[a] < h[b]) s[a] = b;
else if(h[a] > h[b]) s[b] = a;
else {
s[a] = b;
h[b] += 1;
}
}
//别忘记在初始化阶段要将h数组初始化为0；
for(int i = 1; i <= n; i++)
{
s[i] = i;
h[i] = 0;
}经典例题
1. 亲戚问题
题目背景
若某个家族人员过于庞大，要判断两个是否是亲戚，确实还很不容易，现在给出某个亲戚关系图，求任意给出的两个人是否具有亲戚关系。
题目描述
规定：x和y是亲戚，y和z是亲戚，那么x和z也是亲戚。如果x,y是亲戚，那么x的亲戚都是y的亲戚，y的亲戚也都是x的亲戚。
输入格式
第一行：三个整数n,m,p，（n<=5000,m<=5000,p<=5000），分别表示有n个人，m个亲戚关系，询问p对亲戚关系。
以下m行：每行两个数Mi，Mj，1<=Mi，Mj<=N，表示Mi和Mj具有亲戚关系。
接下来p行：每行两个数Pi，Pj，询问Pi和Pj是否具有亲戚关系。
输出格式P行，每行一个’Yes’或’No’。表示第i个询问的答案为 “具有” 或 “不具有” 亲戚关系。
想法：把所有人划分到若干个不相交的集合中，同一个集合里的人彼此是亲戚。为了判断两个人是否为亲戚，只需看它们是否属于同一个集合即可。这个集合我们就可以用并查集来维护。
OK，有了想法之后我们就可以动手来实现了。
2. 村村通
题目描述
某市调查城镇交通状况，得到现有城镇道路统计表。表中列出了每条道路直接连通的城镇。市政府 "村村通工程" 的目标是使全市任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要相互之间可达即可）。请你计算出最少还需要建设多少条道路
输入格式
输入包含若干组测试数据，每组测试数据的第一行给出两个用空格隔开的正整数，分别是城镇数目n和道路数目m；随后的m行对应m条道路，每行给出一对用空格隔开的正整数，分别是该条道路直接相连的两个城镇的编号。简单起见，城镇从1到n编号。
注意：两个城市间可以有多条道路相通。
在输入数据的最后，为一行一个整数0，代表测试数据的结尾。
输出格式
对于每组数据，对应一行一个整数。表示最少还需要建设的道路数目。
3. 修复公路
题目背景
A地区在地震过后，连接所有村庄的公路都造成了损坏而无法通车。政府派人修复这些公路。
给出 A 地区的村庄数N，和公路数M，公路是双向的。并告诉你每条公路的连着哪两个村庄，并告诉你什么时候能修完这条公路。问最早什么时候任意两个村庄能够通车，即最早什么时候任意两条村庄都存在至少一条修复完成的道路（可以由多条公路连成一条道路）。
输入格式
第1行两个正整数N，M。下面M行，每行3个正整数x, y, t，告诉你这条公路连着x, y两个村庄，在时间t时能修复完成这条公路。
输出格式
如果全部公路修复完毕仍然存在两个村庄无法通车，则输出 −1，否则输出最早什么时候任意两个村庄能够通车。
数据范围1 ≤ x,y ≤ N ≤$10^3$，1 ≤ M,t ≤$10^5$。
这是内容