比赛 20160902 评测结果 AAAAAAAATA
题目名称 宗教信仰 最终得分 90
用户昵称 农场主 运行时间 1.353 s
代码语言 C++ 内存使用 3.69 MiB
提交时间 2016-09-02 21:36:38
显示代码纯文本
#include<cstdio>
#include<algorithm>
#define maxn 1000000
using namespace std;
int f[maxn]={0};
void pre(int n){
	for (int i=1;i<=n;i++){
		f[i]=i;
	}
}
int find(int x){
	return x==f[x]?x:f[x]=find(f[x]);
}
void merge(int l,int r){
	f[find(l)]=find(r);
}
int main(){
	freopen("religion.in","r",stdin);
	freopen("religion.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	pre(n);
	for (int i=1;i<=m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		merge(a,b);
	}
	int ans=0;
	for (int i=1;i<=n;i++){
		if (f[i]==i) ans++;
	}
	printf("%d",ans);
}