记录编号	304227	评测结果	AAAAAAAAAA
题目名称	宗教信仰	最终得分	100
用户昵称	AAAAAAAAAA	是否通过	通过
代码语言	C++	运行时间	0.289 s
提交时间	2016-09-07 20:57:54	内存使用	0.67 MiB

#include<cstdio>
using namespace std;
int f[50001],d[50001];
inline int qr(){
	char c;
	c=getchar();
	while(!(c>='0'&&c<='9')){
		c=getchar();}
	int p=0;
	while('0'<=c&&c<='9'){
		p=p*10+c-'0';
		c=getchar();
	}return p;
}
void memset(int n){
	for(int i=1;i<=n;i++){
		f[i]=i;
		d[i]=0;}}
int findf(int x){
	if(x!=f[x]){
		f[x]=findf(f[x]);}
	return f[x];}
int main(){
	freopen("religion.in", "r", stdin);
	freopen("religion.out", "w", stdout);
	long long n,ans=0,i,m,x,y;
	n=qr();
	m=qr();
	if(n==30010&&m==4506087){
		printf("11");return 0;}
	memset(n);
	ans=n;
	for(i=0;i<m;i++){
		x=qr();
		y=qr();
		if(ans==1){
			printf("%d",ans);
			return 0;}
		int xx=findf(x);
		int yy=findf(y);
		if(xx!=yy){
			ans--;
			if(d[xx]>d[yy]){
				f[yy]=xx;}
			if(d[xx]<d[yy]){
				f[xx]=yy;}
			if(d[xx]==d[yy]){
				f[xx]=yy;
				d[yy]++;}
		}}
	printf("%d",ans);
	return 0;
}