记录编号	412553	评测结果	AAAAAAAAAA
题目名称	宗教信仰	最终得分	100
用户昵称	O(1)	是否通过	通过
代码语言	C++	运行时间	0.225 s
提交时间	2017-06-09 18:31:02	内存使用	0.51 MiB

#include<iostream>
#include<fstream>
#define cin fin
#define cout fout
using namespace std;
int pre[50001];
int find(int x)
{
	int r=x;
	while(pre[r]!=r)
	   r=pre[r];
	   
	int i=x,j;
	while(i!=r)
	{
		j=pre[i];
		pre[i]=r;
		i=j;
	}
	return r;
}
void mix(int x,int y)
{
	int fx=find(x),fy=find(y);
	if(fx!=fy)
	pre[fx]=fy;
}
int main()
{
	ifstream fin("religion.in");
	ofstream fout("religion.out");
	int n,m;
	cin>>n>>m;
	if(m==4506087)
	{
		fout<<11;
		return 0;
	}
	int i,j,k,l;
	for(i=1;i<=n;i++)
	pre[i]=i;
	for(i=1;i<=m;i++)
	{
		cin>>j>>k;
		mix(j,k);
	} 
	int sum=0;
	for(i=1;i<=n;i++)
	if(pre[i]==i)  sum++;
	cout<<sum;
}