并查集模板

并查集模板,第1张

并查集模板

模板:

//初始化祖宗就是自己
void init(int x) {
	for(int i=1; i<=x; i++) pre[i]=i;
}

//不停找,直到找到祖宗为止。路径压缩。
int find(int x) {
	if(x==pre[x]) {
		return x;
	}
	return pre[x]=find(pre[x]);
}

//合并子集
void merge(int x, int y) {
	int xx=find(x);
	int yy=find(y);
	if(xx!=yy) {
		pre[xx]=yy;
	}
}
/*
在main函数for循环读取时,默认a为b的祖宗:merge(a,b)

判断a,b有没有公共祖先:
	if(find(a)==find(b)){
		
	}

例题:
L2-010 排座位

#include 
using namespace std;
int n,m,k;
int pre[105],didui[105][105];

void init(int x) {
	for(int i=1; i<=x; i++) pre[i]=i;
}

int find(int x) {
	if(x==pre[x]) {
		return x;
	}
	return pre[x]=find(pre[x]);
}

void merge(int x, int y) {
	int xx=find(x);
	int yy=find(y);
	if(xx!=yy) {
		pre[xx]=yy;
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin>>n>>m>>k;
	init(n);
	while(m--) {
		int a,b,t;
		cin>>a>>b>>t;
		didui[a][b]=didui[b][a]=t;
		if(didui[a][b]==1) {
			merge(a,b);
		}
	}
	
	for(int i=0; i>a>>b;
		if(didui[a][b]==1) {
			cout<<"No problem"<					
										


					

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/3971601.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-10-21
下一篇 2022-10-21

发表评论

登录后才能评论

评论列表(0条)

保存