#include <iostream>
using namespace std;

const int N = 50000;//50000;

int parent[N+1]; // 祖先结点
int rank[N+1];   // 记录节点数

int student;
int pairs;

void InitSet()
{
	int i;
	for (i=1; i<=student; i++)
	{
		parent[i] = i;
		rank[i] = 1;
	}
}

// 找到元素所在的根，并压缩所在集合
// 这样子,经过每一次FindRoot,会相应地改变一些节点的状态, parent和rank都会改变,
// 但是我们只要保证根节点记录的都是正确的就行
int FindRoot(int i)
{
	if (parent[i] != i)
	{
		parent[i] = FindRoot(parent[i]);
	}
	return parent[i];
}


// 按照秩将两个集合按照根来合并

void UnionSet(int root1, int root2)
{
	if (root1 == root2)
	{
		return ;
	}
	if (rank[root2] <= rank[root1])
	{
		parent[root2] = root1;
		rank[root1] += rank[root2];
	}
	else
	{
		parent[root1] = root2;
		rank[root2] += rank[root1];
	}
}


int main()
{
	// student和pairs是全局变量,出现在这里,就覆盖了,导致了InitSet中的student为0
	//int student , pairs; 
	int i, j;
	int x1, x2, root1, root2;

	int testCase = 0;
	while (cin>>student>>pairs && (student | pairs) != 0)
	{
		testCase++;
		InitSet();
		for (i=0; i<=pairs-1; i++)
		{
			cin>>x1>>x2;
			root1 = FindRoot(x1);
			root2 = FindRoot(x2);
			UnionSet(root1, root2);
		}

		int max = student;
		int root ;
		for (i=1; i<=student; i++)
		{
			root = FindRoot(i);
			if (rank[root] != 1)
			{
				max -= rank[root]-1; // 因有共同religion,而使max减少
				rank[root] = 1;
			}
		}
		cout<<"Case "<<testCase<<": "<<max<<endl;
	}
	return 0;
}

• Re:1829MS险过,为什么我的并查集那么费时???哪一位大牛帮我解释一下 (44) stardiy 2009-08-12 09:55:09