【杭电】[3635]Dragon Balls

题意理解起来可能比较费劲
不过可以看出来是一个并查集问题
对模板进行简单的改造以适应题目所需记录的变量

#include<stdio.h>
int par[10200];
int cnt[10200];
int city[10200];
int find(int m) {
    if(par[m]==m)
        return m;
    else {
        int t=par[m];
        par[m]=find(par[m]);
        cnt[m]+=cnt[t];
        return par[m];
    }
}
void unite(int x,int y) {
    x=find(x);
    y=find(y);
    if(x!=y) {
        par[x]=y;
        cnt[x]=1;
        city[y]+=city[x];
        city[x]=0;
    }
}
int main() {
    int T,kase=0;
    scanf("%d",&T);
    while(T--) {
        printf("Case %d:
",++kase);
        int N,Q;
        scanf("%d %d",&N,&Q);
        getchar();
        for(int i=1; i<=N; i++) {
            cnt[i]=0;
            city[i]=1;
            par[i]=i;
        }
        while(Q--) {
            char c;
            scanf("%c",&c);
            if(c=='T') {
                int n,m;
                scanf("%d %d",&n,&m);
                getchar();
                unite(n,m);
            } else {
                int m;
                scanf("%d",&m);
                getchar();
                int t=find(m);
                printf("%d %d %d
",t,city[t],cnt[m]);
            }
        }
    }
    return 0;
}

题目地址:【杭电】[3635]Dragon Balls