并查集（UnionFind）总结

一、并查集-基础版

例题:leetcode-990：等式方程的可满足性

class UnionFind{
private:
    vector<int> parent;
public:
    UnionFind(int n){
        parent.resize(n);
        iota(parent.begin(),parent.end(),0);
    }
    int find(int index){//查找根节点
        if(index==parent[index]) return index;
        parent[index]=find(parent[index]);//所有关联节点的父节点都指向关联的根节点
        return parent[index];
    }

    void unite(int index1,int index2){//关联（将第一个变量的根节点的父节点指向第二个变量的根节点）
        parent[find(index1)]=find(index2);
    }

};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

二、并查集-操作二维数组

只要将二维转化为一维即可比如n*n的矩阵
对于一个坐标为(x,y)的点，对应索引为x*n+y

class UnionFind{
private:
    vector<int> parent;
public:
    UnionFind(int n){
        parent.resize(n);
        iota(parent.begin(),parent.end(),0);
    }
    int find(int index){//查找根节点
        if(index==parent[index]) return index;
        parent[index]=find(parent[index]);//所有关联节点的父节点都指向关联的根节点
        return parent[index];
    }

    void unite(int index1,int index2){//关联（将第一个变量的根节点的父节点指向第二个变量的根节点）
        parent[find(index1)]=find(index2);
    }

};
int main(){
	int m,n;
	cin>>m>>n;
	vector<vector<int>> mat(m,vector<int>(n));
	//...
	UnionFind uf(m*n);
}

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
26
27

三、并查集-获得集合数量

思路：不同的集合，每次合并，都会让集合数量-1
例题:leetcode-547：省份数量

class UnionFind{
private:
    vector<int> parent;
    int setNum;
public:
    UnionFind(int n){
        parent.resize(n);
        iota(parent.begin(),parent.end(),0);
        setNum=n;//初始集合数量为n
    }
    int find(int index){
        if(parent[index]==index) return index;
        parent[index]=find(parent[index]);
        return parent[index];
    }
    void unite(int index1,int index2){
        int p1=find(index1);
        int p2=find(index2);
        if(p1!=p2){//如果两个集合不是同一个，那么合并集合，集合数量减一
            parent[p1]=p2;
            setNum--;
        }
    }
    int getSetNum(){
        return setNum;
    }
};
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
26
27

四、并查集-获得每个集合中元素的数量

每个元素的数量通过size数组，初始化为1（刚开始每个元素都是一个集合）。
我们只把数量保存在父节点上，也就是说size[find(index)]去获取当前index对应的集合数量
只要将子节点的数量全部转移给父节点就行了，然后子节点的数量置空。

通过getSize去获取对应index的集合的元素数量
例题：leetcode-827：最大人工岛

class UnionFind{
public:
    vector<int> parent;
    vector<int> size;
    UnionFind(int n){
        parent.resize(n*n);
        size.resize(n*n,1);
        iota(parent.begin(),parent.end(),0);
    }
    int find(int index){
        if(index==parent[index]) return index;
        return parent[index]=find(parent[index]);
    }
    void unite(int index1,int index2){
        int p1=find(index1),p2=find(index2);
        parent[p1]=p2;
        if(p1!=p2){//如果相等,会出现把size[p1]=size[p2]=0 都清空的异常情况
            size[p2]+=size[p1];
            size[p1]=0;
        }
    }
    int getSize(int index){
        return size[find(index)];
    }
};
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

五、并查集+带权有向图

根本不同的应用场景，权重变化有着不同的传递方式。

下面以leetcode-399：除法求值为例

class UnionFind{
private:
    vector<int> parent;
    vector<double> weight;
public:
    UnionFind(int n){
        parent.resize(n);
        weight.resize(n);
        for(int i=0;i<n;i++){
            parent[i]=i;
            weight[i]=1;
        }
    }
    int find(int index){
        if(index==parent[index]) return index;
        int origin=parent[index];
        parent[index]=find(parent[index]);//同时会把父节点的weight也更新好
        weight[index]*=weight[origin];
        return parent[index];
    }
    void unite(int  index1,int index2,double value){
        int p1=find(index1);
        int p2=find(index2);
        if(p1!=p2){
            parent[p1]=p2;
            weight[p1]=weight[index2]*value/weight[index1];
        }
    }
    double isConnected(int index1,int index2){
        int p1=find(index1);
        int p2=find(index2);
        if(p1==p2){
            return weight[index1]/weight[index2];
        }
        else return -1;
    }
};
//......
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
26
27
28
29
30
31
32
33
34
35
36
37
38