1856.cpp

来自「杭电 acm部分代码 有兴趣的可以下载 谢谢」· C++ 代码 · 共 64 行

#include <iostream>
using namespace std;
int set[10000005];
int num[10000005];
void makeset()
{
	int i;
	for (i = 1; i <= 10000005; i++)
	{
		set[i] = i;
		num[i] = 1;
	}
}
int find(int x)
{
	int i, r = x;
	while (r != set[r])
	{
		r = set[r];
	}
	while (x != r)
	{
		i = set[x];
		set[x] = r;
		x = i;
	}
	return r;
}
void unions(int x, int y)
{
	int a = find(x);
	int b = find(y);
	set[a] = b;
	num[b] += num[a];
}
int main()
{
	int m, a, b, i, cc;
	while (scanf("%d", &m) == 1)
	{
		makeset();
		cc = 1;
		for (i = 1; i <= m; i++)
		{
			scanf("%d %d", &a, &b);
			int aa = find(a);
			int bb = find(b);
			if (aa != bb)
			{
				unions(a, b);
			}
			if (cc < num[aa])
			{
				cc = num[aa];
			}
			if (cc < num[bb])
			{
				cc = num[bb];
			}
		}
		printf("%d\n", cc);
	}
	return 0;
}