/*
 * poj 1988
 */

#include <iostream>
#include <cmath>
using namespace std;

#define N 30008

int t=0; //减去本身； 
int rank[N]={0}, p[N], size[N], value[N], mark[N]={0};

int find( int x ) { 
    if( x==p[x] )
        return (p[x]);
    else
        return find( p[x] );
    }
    
int findx( int x ) {
    
    if( x==p[x] )
        return (t+value[p[x]]);
    t+=value[x];
    return findx( p[x] );
    }
    
void merge( int root1, int root2 ) {
     int x=find( root1 );
     int y=find( root2 );
     if( x==y )
         return ;
     if( rank[x]>rank[y] ) {
         p[y] = x;
         size[x]+=size[y];
         value[x] = value[x]+size[y];
         }
     else{
          p[x] = y;
          //mark[x] = 1;
          value[x] = size[y] - value[y];
          size[y] += size[x];
          //value
          
          
          if( rank[x]==rank[y] )
              rank[y]++;
          }
     }

int main() {
    
    //freopen( "c:\\in.txt" , "r", stdin );
    //freopen( "c:\\out.txt" , "w", stdout );
    
    int n, i, j, k;
    int x, y;
    char c;
    int a, b;
    
    scanf( "%d", &n );
    getchar();
    for( i=1; i<=n; i++ ) {
         p[i] = i;
         value[i]=0;
         size[i] = 1;
         }
    
    for( i=1; i<=n; i++ ) {
         
         scanf( "%c", &c );
         if( c=='M' ) {
             scanf( "%d %d", &x, &y );
             getchar();
             
             a=find( x );
             b=find( y );
             merge(a,b);
             }
         
         else if( c=='C' ) {
              scanf( "%d", &x ); 
              getchar();
              t=0;
              a=findx(x);
              printf( "%d\n", a );
              }
         }
    return 0;
    }

• Re:哪位大牛帮忙看看为什么RE啊?? (1986) lili_922 2008-11-28 20:14:14
• Re:哪位大牛帮忙看看为什么RE啊?? (1986) lili_922 2008-11-28 20:14:15