本题可用标准并查集解，但是因为数量huge，决定采用带压缩路径的并查集，忽然发现scanf和printf是要比cin和cout好得多，多次TLE之后得出的结论。

//2120505  	2010-03-21 15:16:12  	  Time Limit Exceeded  	2833  	C++  	3001  	964  	
//2120523  	2010-03-21 15:23:52  	  Time Limit Exceeded  	2833  	C++  	3001  	964
//2120603  	2010-03-21 16:26:17  	  Accepted  	       2833  	C++  	260  	964
//zju2833(Friendship)
//http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1833
/*
所谓的带压缩路径就是在这个树完成了find操作之后，高度至多为2，而且形式为跟节点下面有cnt咯叶子
在完成二个树合并之后高度至多为3
*/
#include <iostream>
#include <cstdio>
using namespace std;

const int N = 100002;

typedef struct
{
	int parent;//记录前驱
	int cnt;//记录集合元素个数
}Node;

Node UFSet[N];
int n, m;

void init()
{
	for(int i = 0; i <= n; i++)
	{
		UFSet[i].parent = i;
		UFSet[i].cnt = 1;
	}
}

int find(int x)
{//带压缩路径
	int y = x, tmp;
	while(UFSet[y].parent != y)
		y = UFSet[y].parent;
	while(x != y)
	{
		tmp = UFSet[x].parent;
		UFSet[x].parent = y;
		x = tmp;
	}
	return y;
}

void merge(int x, int y)
{
	x = find(x);
	y = find(y);
	if(x == y)
		return;
	if(UFSet[x].cnt > UFSet[y].cnt)
	{
		UFSet[y].parent = x;
		UFSet[x].cnt += UFSet[y].cnt;
	}else
	{
		UFSet[x].parent = y;
		UFSet[y].cnt += UFSet[x].cnt;
	}
}
int main()
{
	int tc = 1;
	bool flag = false;
	char cmd;
	int i;
	int a, b;
	while(cin>>n>>m)
	{
		init();
		if(flag)
			printf("\n");
		printf("Case %d:\n",tc);
		//cout<<"Case "<<tc<<":"<<endl;
		for(i = 0; i < m; i++)
		{
			//cin>>cmd;
			getchar(); 
			cmd = getchar();
			if(cmd == 'M')
			{
				//cin>>a>>b;
				scanf("%d%d", &a, &b);
				merge(a, b);
			}
			else
			{
				//cin>>a;
				scanf("%d", &a);
				printf("%d\n", UFSet[find(a)].cnt);
				//cout<<UFSet[find(a)].cnt<<endl;
			}
		}
		tc++;
		flag = true;

	}
	return 0;
}

• 相关文章
• 全局相关文章