比赛 至少完成十道练习 评测结果 AAAAAAAAAA
题目名称 宗教信仰 最终得分 100
用户昵称 Menamovic 运行时间 0.707 s
代码语言 C++ 内存使用 0.67 MiB
提交时间 2017-05-23 08:30:48
显示代码纯文本
#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;
}