记录编号	407876	评测结果	AAAAAAAAAA
题目名称	宗教信仰	最终得分	100
用户昵称	Menamovic	是否通过	通过
代码语言	C++	运行时间	0.713 s
提交时间	2017-05-23 08:32:17	内存使用	0.67 MiB

#include <cstdio>
#define Nmax 50003
inline int get_n() 
{
	char c;
	c = getchar();
	while (!('0' <= c && c <= '9'))
		c = getchar();
	int a = 0;
	while ('0' <= c && c <= '9') 
	{
		a = a*10+c-'0';
		c = getchar();
	}
	return a;
}
int N, M;
int ans;
int fa[Nmax];
int rk[Nmax] = {0};
int FA(int x) 
{
	if (fa[x] == x)
		return x;
	return fa[x] = FA(fa[x]);
}
int main()
{
	freopen("religion.in", "r", stdin);
	freopen("religion.out", "w", stdout);
	N = get_n();
	M = get_n();
	ans = N;
	for (int i = 1; i <= N; i++)
		fa[i] = i;
	int a, b;
	int af, bf;
	for (int i = 0; i < M; i++) 
	{
		if (ans == 1)
			break;
		a = get_n();
		b = get_n();
		af = FA(a);
		bf = FA(b);
		if (af != bf) 
		{
			ans--;
			if (rk[af] == rk[bf]) 
			{
				fa[af] = bf;
				rk[bf]++;
			}
			else if (rk[af] > rk[bf])
				fa[bf] = af;
			else
				fa[af] = bf;
		}
	}
	printf("%d\n", ans);
	return 0;
}