这大概就是所谓的RPWT，拿出来炫耀一下。【灰溜溜爬开】

其实这题的时限是3000ms，还宽裕的很。但前十名都能把时间压到500ms以内，说明普通的并查集还有值得优化的地方。顺便讲一句，这题通过的人数好X多。第一次写的时候根本就忘了什么是压缩路径，可耻地TLE鸟。【= =】 发现上一次写并查集是一年前的事情，结果又忘记怎么做了……【为什么是又】

所谓的并查集，也只不过是一枚特殊的树罢了。这棵树在完成findset操作之后，高度至多为2，而且形式为根节点下面N个叶子——这就是压缩；在完成两棵树的合并之后高度至多为3.为了方便编写，采用的是数组而不是链表；这一点我倒是牢牢记住了。

/* zoj 2833
 author : Crux.D
 date : 2008.1.21
 description : unionset
*/

#include <cstdio>
#include <string>

int parent[100001], num[100001], N, M, cs = 0;

void init ()
{
 int i;
 for ( i = 0; i <= N; i ++ )
 {
  parent[i] = -1;
  num[i] = 1;
 }
 if ( cs ++ )
  printf ( "\n" );
 printf ( "Case %d:\n", cs );
}

int find_set ( int n )
{
 //寻找树的根节点
 int pre = n;
 while ( parent[pre] != -1 )
 {
  pre = parent[pre];
 }
 int root = pre;
 //非递归从底到顶压缩路径，简化为高度为2的树
 while ( n != root )
 {
  int t = parent[n];
  parent[n] = root;
  n = t;
 }
 return root;  
} 

int union_set ( int n1, int n2 )
{
 int t1 = find_set ( n1 );
 int t2 = find_set ( n2 );
 //合并之后树的高度为3，小树合至大树
 if ( t1 == t2 )
  return 0;
 if ( num[t1] < num[t2] )
 {
  parent[t1] = t2;
  num[t2] += num[t1];
 }
 else
 {
  parent[t2] = t1;
  num[t1] += num[t2];
 }
 return 0;
}

void query_friend ( int n )
{
 int t = find_set ( n );
 printf ( "%d\n", num[t] );
}

int main ()
{
 //freopen ( "in.txt", "r", stdin );
 
 while ( scanf ( "%d %d ", &N, &M ) != EOF )
 {
  int i;
  init ();
  for ( i = 0; i < M; i ++ )
  {   
   char ch;
   int t1, t2 = 0;
   scanf ( "%c", &ch );
   if ( ch == 'M' )
   {
    scanf ( "%d %d ", &t1, &t2 );
    union_set ( t1, t2 );
   }
   else
   {
    scanf ( "%d ", &t1 );
    query_friend ( t1 );
   }
   //pt ();
   //printf ( "%c %d %d\n", ch, t1, t2 );
  }  
 }

 return 0;
}

评论