并查集模板

模板：

//初始化祖宗就是自己
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