并查集

定义

并查集是一种树形数据结构，用于处理一些不相交集合的合并，查询问题。

主要构成

一个数组pre[]pre[ ]，记录了每个点的前驱节点是谁；

两个函数：find(x)find(x)，用于查找指定节点属于哪个分支（集合）；join(x,y)join(x,y)，合并两个节点；

作用

求连通分支数（一个图中互不连通的连通子图数）；

意义

当我们判断两点是否连通时，可以往根部进行查找，只要两点可由相同的一点的分支下来那么两点就是连通的。

用集合中某个元素来代表这个集合，则该元素称为此集合的代表元。

实现

pre[]

我们用一个数组来记录每节点的前驱，比如pre[5]=6pre[5]=6代表5号节点的前驱节点是6号节点。如果一个节点的前驱节点是它自己，则说明此节点为根节点。

find(x)

查找xx所在分支的根节点，从xx开始通过pre[x]pre[x]获取它的前驱节点，重复获取直到抵达根节点。

1
2
3
4
5
6
7
8
int find(int x)
{
	while(pre[x]!=x)
    {
        x = pre[x];
    }
    return x;
}

join(x,y)

合并x,yx,y​节点，只需要让两节点对应的根节点在同一集合下即可。如果两根节点为同一节点则无需操作，否则从二者中选择一个节点作为根节点。

1
2
3
4
5
6
7
8
9
10
void join(int x, int y)
{
    int root_x = find(x);
    int root_y = find(y);
    
    if(root_x != root_y)
    {
        pre[root_x] = root_y;
    }
}

这里我们在合并的时候全部选择yy的根节点作为共同根节点，但是这可能会导致最后的树形结构某一分支过长。此时我们可以通过记录每个节点所在的高度，在最后合并的时候选择高度较为高的作为根节点，如果高度相等，在选择根节点之后需要将该节点的高度+1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
void join(int x, int y)
{
    int root_x = find(x);
    int root_y = find(y);
    
    if(rank[root_x] == rank[root_y])
    {
        rank[root_x]++;
        pre[root_y] = root_x;//可根据具体情况选择
    }
    else if(rank[root_x]>rank[root_y])
    {
        pre[root_y] = root_x;
    }
    else
    {
        pre[root_x] = root_y;
    }
}

注意：此处的高度也可换为其他需要的数据。