题解 | 村村通工程

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;

int n,m;
int fa[N];

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

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

void add(int x,int y){
	int fx=find(x);
	int fy=find(y);
	if(fx==fy) return;
	else{
		fa[fx]=fy;
	}
	return;
}

int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	
	cin>>n>>m;
	pre();
	int u,v;
	for(int i=1;i<=m;i++){
		cin>>u>>v;
		add(u,v);
	}
	
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(fa[i]==i){
			cnt++;
		}
	}
	
	cout<<cnt-1<<endl;

    return 0;
}