2414423_ac_4187ms_448k.cc

来自「北大大牛代码 1240道题的原代码 超级权威」· CC 代码 · 共 38 行

#include <stdio.h>
#include <string.h>
int res[50002], mark[50002];

int main()
{
	int n, m, ans, t;
	int a, b, i, j, cas;
	
	cas = 1;
	while(scanf("%d%d",&n,&m)==2)
	{
		if(!m&&!n)
			return 1;
		for(i = 0; i <= n; i++)
			res[i] = i;
		ans = 0;
		memset(mark,0,sizeof(mark));
		for(i = 0; i < m; i++)
		{
			scanf("%d%d",&a,&b);
			t = res[b];
			if(res[a]==res[b])
				continue;
			for(j = 1; j <= n; j++)
			{
				if(res[j]==t)
					res[j] = res[a];
			}
		}
		for(i = 1; i <= n; i++)
			if(mark[res[i]]==0)
				mark[res[i]] = 1,ans++;
		printf("Case %d: %d\n",cas++,ans);	
	}
	return 1;
}