并查集是一种树型的数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题。常常在使用中以森林来表示。
举个例子，某乡镇有多个村子，为了出行方便，需要进行修路，使所有村子连在一起。
某乡镇
现在，按照如下pair修路，按顺序如果两村之间已经可以互相到达则不需要再修路。（不将就距离问题，只看是否连通）
1.5 2.4 1.6 6.7 1.7 3.4 3.6 1.2
路线
如图进行连接 ，绿色的为修路的路线，红色的为按顺序不必要修的路线。
整体路线大概为2-4-3-6-1（7）-5。
正如标题所说，形成的一种树状图形，其中节点6的度为2。
那么问题来了，我们如何才能知道，这个两个节点是否已经是连在一条线上的呢？
这里我们采用数组的方法来解决。
首先，我们需要一个数组，数组的下标即是村庄（节点）。然后，我们的到需要修路的村庄pair，我们先惊醒判定，如果两村庄不在一条线上，就绑在一条线上（绑定方法为找头），如果已经在一条线上，就不做处理。
找头的时候，我们需要先对数组进行初始化，初始化为数组的值为数组的下标。而这个下标节点对应的值便是这个节点的上级头目，一直向上寻找，当下标节点的值等于下标时，便是头。
for(int i = 0; i < n; i++)
v[i] = i;
然后，我们通过调用函数的方式，对得到的一组村庄进行判定，如果二者的头是同一个数组下标，则为统一条线的村庄，如果头的下标不同，则是两条不同的线，可以进行连线。
连线的方式也很普通，由于找头之后，节点目前的位置在头处，只需将其中一个头连接到另一个头上即可。
int getf(int v){
if(v == f[v])
return v;
return f[v] = getf(f[v]);
}
void merge(int v,int u){
int t1 = getf(v);
int t2 = getf(u);
if(t1 != t2)
f[t1] = t2;
}
不必担心，两个头谁连接到谁的问题，因为都是头，无论谁连接到谁，被连接的部分不变，连接的部分得到一个新头。如图所示：
图中，1与2已经相连，需要对2和3进行连接，已经查到2的头为1（f【2】=1，f【1】=1），3的头为3（f【3】=3），我们得到两种连接方式，分别为
1、连接结果为f【2】=1 f【1】=1 f【3】=1 2（3）-1
2、连接结果为f【2】=1 f【1】=3 f【3】=3 2-1-3
按照以上操作将需要处理的数据处理完，我们就通过并查集获得多条线（称为树更合适），这些线在一起，组成森林，我们通过遍历的方式，对每个数组下标进行遍历，如果此下标的头第一次出现，计数器++，如果已经出现，跳过，遍历结束，我们即可得到森林里有多少颗树。
并查集可以做很多题目
1.畅通工程（修路）
2.食物链判断
3.判断是否为树
4.将很多人按照熟悉的人进行分组
等等。。。
by：有我wa
网友评论