〔C++算法分析〕并查集

        并查集是一种树型的数据结构，用于处理一些不相交集合（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