一道非常简单的并查集题目,只需要把每组人均合并到一起。最后统计和 0 是一个父亲的数量即可,20 分钟 Accepted.

/* POJ 1611
 * By Ceeji
 * Union
 */
 
#include <iostream>
#include <cstring>
 
using namespace std;
 
#define MAX_N 30000
 
int m, n;
 
int father[MAX_N];
 
int get_father(const int p)
{
	if (father[p] == -1 || father[p] == p)
	{
		father[p] = p;
		return p;
	}
	father[p] = get_father(father[p]);
	return father[p];
}
 
void set_union (const int x, const int y)
{
	int fx = get_father (x);
	int fy = get_father (y);
	father[fx] = fy;
}
 
void do_work ()
{
	for (int i = 0; i < MAX_N; ++i)
		father[i] = -1;
	for (int j = 0; j < m; ++j)
	{
		int gn, tmp, first;
		cin >> gn >> first;
		for (int i = 0; i < gn - 1; ++i)
		{
			cin >> tmp;
			if (get_father(tmp) != get_father(first))
				set_union (tmp, first);
		}
	}
	int f = get_father(0);
	int num = 0;
	for (int i = 0; i < n; ++i)
	{
		if (get_father(i) == f)
			++num;
	}
	cout << num << endl;
}
 
int main ()
{
	while (true)
	{
		cin >> n >> m;
		if (m == 0 && n == 0)
			return 0;
		do_work ();
	}
	return 0;
}