pku1611.cpp

来自「这是ACM 方面的资料 是PKU的 北京大学的出来的」· C++ 代码 · 共 69 行

#include <stdio.h>

int p[30010];
int n, m;

int getid(int k)
{
	int root;
	if (p[k] == k)
	{
		return k;
	}
	
	root = getid(p[k]);
	p[k] = root;
	return root;
}

void pre()
{
	int i;
	for (i = 0; i <= n; i++)
	{
		p[i] = i;
	}
}

int main()
{
	int i, j, head, tmp, num, sum;

	while (scanf("%d%d", &n, &m) != -1)
	{
		if (m == 0 && n == 0)
		{
			break;
		}

		pre();

		for (j = 0; j < m; j++)
		{
			scanf("%d %d", &num, &head);
			for (i = 1; i < num; i++)
			{
				scanf("%d", &tmp);
				if (p[tmp] == tmp)
				{
					p[tmp] = getid(head);
				}
				else
				{
					p[getid(head)] = getid(tmp);
				}
			}
		}

		for (i = 0, sum = 0; i < n; i++)
		{
			if (getid(i) == getid(0))
			{
				sum++;
			}
		}
		printf("%d\n", sum);
	}
	
	return 0;
}