hdu 3635 Dragon Balls

点击打开hdu 3635

思路: 并查集
分析:
1 题目说有n个城市每一个城市有一个龙珠编号为i，现在有m行的输入包括两种的情况
T x y 把x所在的集合的所以龙珠转移到y集合上 Q x 询问x所在集合的龙珠的个数
2 我们利用rank[x]表示的是根节点为x的集合的元素的个数，但是现在我们发现求转移的次数不好求，刚开始我用的是一个vector数组来保存，比如v[x]表示以x为根节点的集合的元素，那么如果是把fx这个集合并到fy上的话，那么我们枚举v[fx]。但是这个方法TLE了
3 后来看了网上的题解，发现在求转移次数的时候我们也可以利用递归合并的思想，比如把fx所在的集合转移到fy的时候，那么我们只要把fx的转移次数加一，那么下次递归的时候我们在里面进行处理即可

代码:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;

const int MAXN = 10010;

int n , m;
int father[MAXN];
int rank[MAXN];
int num[MAXN];

void init(){
    memset(num , 0 , sizeof(num));
    for(int i = 0 ; i <= n ; i++){
        father[i] = i;
        rank[i] = 1;
    }
}

int find(int x){
    if(father[x] != x){
       int fa = father[x];
       father[x] = find(fa);
       rank[x] += rank[fa];
       num[x] += num[fa];
    }
    return father[x];
}

void Union(int x , int y){
    int fx = find(x);
    int fy = find(y);
    if(fx != fy){
        father[fx] = fy;
        rank[fy] += rank[fx];
        num[fx]++;
    }
}

void solve(int x){
    int fx = find(x);
    printf("%d %d %d\n" , fx , rank[fx] , num[x]);
}

int main(){
    int cas , Case = 1;
    char c;
    int x , y;
    scanf("%d" , &cas);
    while(cas--){
         scanf("%d%d%*c" , &n , &m);
         init();
         printf("Case %d:\n" , Case++);
         while(m--){
              c = getchar();
              if(c == 'T'){
                  scanf("%d%d%*c" , &x , &y);
                  Union(x , y);
              }
              else{
                  scanf("%d%*c" , &x);
                  solve(x);
              }
         }
    }
    return 0;
}