并查集操作

小鱼儿 2021-09-21 06:06 313阅读 0赞

## 并查集 ##

> 并查集可以简单的看作是对集合的“合并和查找”。每一个元素都唯一属于一个集合，每一个集合都有唯一的一个根元素，来唯一标识这个集合。

如何储存元素？

可以用数组来存储元素，数组下标代表该元素，数组的值代表该元素的父元素。例如Father\[a\] = b。就代表a元素的父元素是b。

如何表示根元素？

规定一下，只要Father\[i\] = i ,则代表i为该集合的根元素。

并查集的两个基本操作就是查找和合并。查找：就是查找该元素的父元素。合并：合并两个集合，可以简化为合并两个集合的根节点。

查找操作

int findFather(int a){ //查找a元素的父元素
        while(a != father[a]){
            a = father[a];
        }
        return a;
    }

合并操作

void Union(int a, int b){ 
    	int fatherA = findFather(a);
    	int fatherB = findFather(b);
    	if(fatherA != fatherB){
    		father[a] = b;
    	}
    }

并查集的两种常见的问题是：1）求集合数 2)求每个集合中的元素个数

这两种问题都可以通过一个数组来解决。

对于求集合数，可以开一个布尔型的数组isRoot，数组的初始的值都为false。在进行完合并的操作之后。遍历一下所有的元素的父元素，标记为true即可。

for(int i=1; i<=n; i++){ 
        isRoot[findFather[i]] = true;
    }
    
    int ans = 0;
    for(int i=1; i<=n; i++){ 
        ans += isroot[i];
    }
    //ans的值就位集合的个数

对于求每一个集合中的元素个数，只需要将上面的isRoot数组的类型改为int型，初始化为0，然后在遍历每一个元素的父元素时累加即可。

for(int i=1; i<=n; i++){ 
        isRoot[findFather[i]]++;
    }
    //isRoot[i] 的值代表以i为根节点的集合的元素的个数

并查集模板

#include<cstdio>
    #include<algorithm>
    using namespace std;
    const int maxn = 1010;
    int n;//人数
    int father[maxn];
    int isRoot[maxn]={ 0};
    
    //初始化
    void initialize(int n){ 
    	for(int i=1; i<=n; i++){ 
    		father[i] = i;
    	}
    }
    
    //查找根元素
    int find_Father(int x){ 
    	int a = x;
    	while(x != father[x]){ 
    		x = father[x];
    	}
    	//路径压缩
    	
    	while( a  != father[a]){ 
    		int t = father[a];
    		father[t] = x;
    		a = father[a];
    	}
    	return x; 
    }
    
    //合并
    void Union(int a, int b){ 
    	int fatherA = find_Father(a);
    	int fatherB = find_Father(b);
    	if(fatherA != fatherB){ 
    		father[fatherA] = fatherB;
    	}
    }