[开发测试]并查集原理

并查集核心原理

#include <cstdio>
#include <iostream>
using namespace std;

int n, m, k, sum = 0;//m:关系个数   n：结点个数 
int f[1000] = {0};

void init(){
	for(int i = 0; i <= n; i++)
		f[i] = i;
}

int getf(int v){//找到集合的代表：Boss 
	if(f[v] == v) return v;
	else{
		f[v] = getf(f[v]);//路径压缩 即在回溯的过程中，将遇到的元素的Boss改为终极Boss 
		return f[v];      //路径压缩不会增加时间复杂度   
	}					  //压缩能提高以后找某个元素的Boss的速度 
} 

void merge(int v, int u){//合并子集合
	//找到各自的Boss  直接修改Boss之间的关系 
	int t1 = getf(v); 
	int t2 = getf(u);
	if(t1 != t2) f[t2] = t1;//靠左原则 
}
int main()
{
	int x, y;
	freopen("3.txt", "r", stdin);
	cin >> n >> m;//n个点，m个关系
	init();
	for(int i = 1; i <= m; i++){
		cin >> x >> y;
		merge(x, y);
	}
	
	for(int i = 1; i <= n; i++)
		if(f[i] == i) sum++;
	cout << sum << endl;
	cout << f[6];
	return 0;
}

测试用例

10 9
1 2
3 4
5 2
4 6
2 6
8 7
9 7
1 6
2 4

结果
3

相关题目

• 岛屿数量