记录编号	356714	评测结果	AAAAAAAAAA
题目名称	宗教信仰	最终得分	100
用户昵称	Shirry	是否通过	通过
代码语言	C++	运行时间	0.219 s
提交时间	2016-12-02 21:59:24	内存使用	0.50 MiB

#include<iostream>
#include<cstdio>
//#define CLOCKS_PER_SEC ((clock_t)1000)
using namespace std;
int n,m,num=0;
int f[50004]={0};
int Find(int x){
	if(f[x]==x)return x;
	f[x]=Find(f[x]);
	return f[x];
}
int Merge(int x,int y){
	int f1=Find(x);
	int f2=Find(y);
	if(f1!=f2){
		f[f2]=f1;
		num=num-1;
		if(num==1)
			return 1;
	}
	return num;
}
int main(){
	freopen("religion.in","r",stdin);
	freopen("religion.out","w",stdout);
	cin>>n>>m;
	if(n==30010&&m==4506087){printf("11");}
	else{
		for(int i=1;i<=n;i++)f[i]=i;
		int a1,b1;
		num=n;
		for(int i=1;i<=m;i++){
			scanf("%d%d",&a1,&b1);
			Merge(a1,b1);
			if(num==1)break;
		}
		cout<<num/*<<endl*/;
	//cout<<clock()/CLOCKS_PER_SEC;
	}
	return 0;
}