Luogu P1536 村村通

Luogu P1536 村村通

很简单的并查集。
记住$道路数=区块数-1$。

#include<bits/stdc++.h>
#define N 1010

using namespace std;

int n,m,ans;
int fa[N];

int Find(int x) {
	return fa[x]==x?x:fa[x]=Find(fa[x]);
}

void Merge(int x,int y) {
	fa[Find(y)]=Find(x);
	return;
}

void Init() {
	for(int i=1;i<=n;i++) {
		fa[i]=i;
	}
	ans=0;
	return;
}

void Read() {
	scanf("%d",&m);
	for(int i=1;i<=m;i++) {
		int u,v;
		scanf("%d%d",&u,&v);
		Merge(u,v);
	}
	return;
}

void Solve() {
	for(int i=1;i<=n;i++) {
		if(fa[i]==i) {
			ans++;
		}
	}
	printf("%d
",ans-1);
	return;
}

int main()
{
	while(scanf("%d",&n)&&n) {
		
		Init();
		Read();
		Solve();
	}
	return 0;
}