并查集

初识并查集

并查集是一种数据结构，其作用是判断两个元素是否属于同于一个集合。例如存在a，b，c，d，e五个元素，其中a，b，c同属于一个集合，d和e属于另一个集合。如果我们实现一种查找，输入a输出0，输入b输出0，输入c输出0那么就可以判断abc是属于同于个集合因为对它们进行查找输出的都是同样的结果，同理输入d输出3，输入e输出3也可以判断它们是同一个集合。

那么并查集需要如何实现呢？同样使用上面的例子，首先对a，b，c，d，e进行标识0,1,2,3,4用它们来作为数组parent的下标并初始化数组元素的值等于其索引值即parent=[0,1,2,3,4]，接下来是最为重要的关联操作：我们需要将abc关联起来，只需要使得b指向a，c指向b就可以了。这样查找b的时候就可以顺着指向查找到a，查找c可以顺着指向查找到b最后找到a，a指向a（需要注意的是这个指向操作是有序的）。要实现这个操作只需要将数组parent[1]的值改为0吗，parent[2]的值改为1就可以了，这个时候数组变为了parent=[0,0,1,3,4]，例如查找c是否与a同属于一个集合，首先查找c因为c标识的是2，所以对应的其在数组中的值是parent[2]也就是1，由于parent[2]的值不是2而是1可以理解为c指向的不是c而是b，那么我们继续查找b直至最后查找出根元素，b的标识为1对应的元素值为parent[1]=0,也就是b指向的不是b而是a，继续查找a，a的标识为0对应的数组值为parent[0]=0也就是a指向的是a也就是其本身结束查找，最终可以由c查找到a。同理需要查找c与b是否同属于一个集合，查找c最终的结果会是a，查找b最终的结果也会是a那么他们就是同属于一个集合。

需要注意的是并查集的关联操作是一个有序的关联，不能b指向a，a指向b，c指向b。并且在实际使用并查集的时候我们可以一些技巧来加快查找速度，例如上面的例子中c指向b，b指向a。那么查找c时需要经过b才可以到达结果a，这个时候可以使得c直接指向a减少查询的步骤。下面就提供了一个路径压缩的并查集模板，在看这个模板之前需要对递归有一定的理解。

路径压缩模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class UnionFind{
    int[] parent;
    
    //构造函数初始化数组parent
    public UnionFind(int n){
        parent=new int[n];
        for(int i=0;i<n;i++){
            parent[i]=i;
        }
    }
    
    //合并操作也就是关联操作
    public void union(int index1,int index2){
        parent[find(index1)]=find(index2);
    }
    
    //查找操作
    public int find(int index){
        //parent[index]!=index说明index指向的不是其本身也就不是根元素
        if(parent[index]!=index){
            parent[index]=find(parent[index]);
        }
        return parent[index];
    }
}

这个模板可以理解并记忆起来，在以后碰到有关联需要的题目时可以考虑并查集，最后强烈建议把推荐的并查集题目做完。

并查集题目练习