C++ 并查集模板

#include <iostream>
#include <algorithm>
#define MAXN 1000
#define debug(x) (cout << #x << ":" << x << endl)

using namespace std;

int f[MAXN];


//寻找根节点 
int find(int x){
	if(x != f[x]) f[x] = find(f[x]);
	return f[x];
}


//合并两个节点
void merge(int a, int b){
	int pa = find(a);
	int pb = find(b);
	if(pa != pb){
		f[pa] = pb;
	}
	
	
}

//初始化 
void init(){
	for(int i = 0; i < MAXN; i++)
		f[i] = i;
}

int main(){
	init();//初始化后,每个节点的父节点就是本身,如:f[1] = 1 
	
	
	//1为根节点的集合 
	f[2] = 1;
	f[3] = 2;
	f[4] = 3;
	f[5] = 4;
	
	
	//6为根节点的集合 
	f[7] = 6; 
	f[8] = 7;
	
	
	//此时存在以1为根节点的集合,和以6为根节点的集合 
		
	
	//5的父节点是4,4的父节点是3,以此类推
	//到1的时候正好父节点和节点本身相等,那么1就是所有节点的根节点 
	cout<<find(1)<<endl;
	cout<<find(2)<<endl;
	cout<<find(3)<<endl;
	cout<<find(4)<<endl;
	cout<<find(5)<<endl;
	
	//和上面一样6是所有节点的根节点 
	cout<<find(7)<<endl;
	cout<<find(8)<<endl;
	
	return 0;
	
}


本文标题:《C++ 并查集模板》作者:Scar
原文链接:https://aki.cc/post/9.html
特别注明外均为原创,转载请注明。

分享到微信

扫描二维码

可在微信查看或分享至朋友圈。

相关文章

发表评论:

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。