2730205 2008-01-22 18:15:30 Accepted 2833 C++ 00:00.95 1180K C.D.   这大概就是所谓的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;}

评论