【并查集】POJ-1611

/* POJ-1611 并查集（基础题）
①带路径压缩的查找
②合并：先判断是否在同一集合，合并操作执行的条件是2元素不在同一集合
*/
#include <stdio.h>
#define N 30001
int set[N];
int elemNum[N];
void initialize(int n);
int findSet(int a);
void unionSet(int a, int b);
	
int main()
{
	int n, m;
	int array[N];
	int i, k, j;
	while(scanf("%d%d", &n, &m) == 2)
	{
		if(n == 0 && m == 0)
		{
			break;
		}
		initialize(n);
		for(i = 0; i < m; i++)
		{
			scanf("%d", &k);
			scanf("%d", array);
			for(j = 1; j < k; j++)
			{
				scanf("%d", array+j);
				unionSet(array[j-1],array[j]);
			}
		}
		printf("%d\n", elemNum[0]);
	}
	return 0;
}
//initialize
void initialize(int n)
{
	int i;
	for(i = 0; i < n; i++)
	{
		set[i] = i;//每一个元素都是一个集合，所在集合的代表元素也为自己
		elemNum[i] = 1;//每个集合里有1个元素
	}
}
/* 带路径压缩的集合寻找
比较难设计的递归
*/
int findSet(int a)
{
	if(a == set[a])//这是集合代表元素的标志
	{
		return set[a];
	}
	else
	{
		//相当巧妙，不光找到了根节点，并且将后代节点直接指向了根节点，方便了后续查找，这就是路径压缩
		set[a] = findSet(set[a]);
		return set[a];
	}
}
//合并集合
void unionSet(int a, int b)
{
	int seta, setb;
	seta = findSet(a);
	setb = findSet(b);
	if(seta == setb)//【极易忽略】2个数已经在同一集合
	{
		return;
	}
	if(seta == 0)
	{
		elemNum[0] += elemNum[setb];
		set[setb] = 0;//将集合setb加入到集合0中
		return;
	}
	if(setb == 0)
	{
		elemNum[0] += elemNum[seta];
		set[seta] = 0;
		return;
	}
	if(elemNum[seta] >= elemNum[setb])
	{//将小集合加入到大集合里
		elemNum[seta] += elemNum[setb];
		set[setb] = seta;
	}
	else
	{
		elemNum[setb] += elemNum[seta];
		set[seta] = setb;
	}
}