GitBook

这里写图片描述 这里写图片描述

体验一把套模板的毫无意义的爽快感 虽然这题很早以前就做过 但这次用了压缩路径加防退化

哎呀…… 这套用的我都不知道把题解直接写在并查集说明 还是写到这里了……

就这一题而言…… 我勒个去…… 没什么说的 标准的并查集 看并查集的说明吧 【看书】并查集——合并与查询

然后输出的是 总集合数-1 便可达到畅通

#include<stdio.h>
int par[1020];
int rank[1020];
int find(int m) {
	if(par[m]==m) {
		return m;
	} else
		return par[m]=find(par[m]);
}
void unite(int x,int y) {
	x=find(x);
	y=find(y);
	if(x==y)
		return;
	else {
		if(rank[x]<rank[y]) {
			par[x]=y;
		} else {
			par[y]=x;
			if(rank[x]==rank[y])
				rank[x]++;
		}
	}
}
int main() {
	int N,M;
	while(scanf("%d", &N),N) {
		scanf("%d", &M);
		for(int i=1; i<=N; i++) {
			par[i]=i;
			rank[i]=0;
		}
		while(M--) {
			int u,v;
			scanf("%d %d",&u,&v);
			unite(u,v);
		}
		int cnt=0;
		for(int i=1; i<=N; i++) {
			if(par[i]==i)
				cnt++;
		}
		printf("%d\n",cnt-1);
	}
	return 0;
}

题目地址:【杭电】[1232]畅通工程