beloved_ACM

SB,NB,都是一个B.
posts - 29, comments - 2, trackbacks - 0, articles - 0
  C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合  :: 管理

Dragon_Balls_简单并查集

Posted on 2011-09-09 11:39 成幸毅 阅读(234) 评论(0)  编辑 收藏 引用
#include <iostream>
#include 
<cstdio>
#include 
<cstdlib>
#include 
<cstring>
#include 
<string>
#include 
<queue>
#include 
<vector>
#include 
<algorithm>
using namespace std;

const int MAXN = 10010;
int n,m;
int father[MAXN], rank[MAXN], a,b;
int depth[MAXN],t;
void make() {
     
   
for(int i = 1; i <= n; i++{
      father[i] 
= i;
      rank[i] 
= 1;
      depth[i] 
= 0;
   }

}


int _find(int x) {
    
    
int h = x;
    t 
= 0;
    
while(h != father[h]) {
       t 
= t + depth[h];
       h 
= father[h];
       
    }

        
    
int y;
    
int tmp;
    
while(x != h) {
       t 
-= depth[x];
       depth[x] 
+= t;
       y 
= father[x];
       father[x] 
= h;
       x 
= y;
    }

    
return h;
}


void _union(int a,int b) {
     
     
int x = _find(a);
     
int y = _find(b);
     
       rank[y] 
+= rank[x];
       depth[x] 
= 1;
       father[x] 
= y;
}


char type;

int main() {
    
    
int cas;
    
while(scanf("%d",&cas) != EOF) {
    
for(int acase = 1; acase <= cas; acase++){
       scanf(
"%d%d",&n,&m);
       printf(
"Case %d:\n",acase);//<<":"<<endl;
       make();
       
for(int i = 0; i < m; i++{
          
          scanf(
"\n%c",&type);
          
if(type == 'T'{
             scanf(
"%d%d",&a,&b);
             _union(a,b);
            
          }

          
else {
             scanf(
"%d",&a);
             
int tmp = _find(a); 
             printf(
"%d %d %d\n",tmp,rank[tmp],depth[a]); 
            
// cout<<tmp<<" "<<rank[tmp]<<" "<<depth[a]<<endl;;
          }

       }

    }

    }

        
    
//system("pause");
    return 0;
}


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理