hdu3635 Dragon Balls

乍一看还以为是线段树什么的。。

有两个操作：

T A B 表示把A球所在的城市里所有球添加到B球所在的城市

Q A 表示 输出A所在的城市，A所在的城市里的球的个数，A转移了几个城市

前两个输出比较简单，关键是最后一个

好在题目给的是 球代表的城市进行转移，这就说明，一个城市最多只能转移一次（之后就为空，就再也无法转移或被转移了），相当于问A所在的城市被合并了几次

那么移动次数可以在路径压缩时更新

最开始，所有球move=0,

选择了一个球的城市全部转移，则该城市所有球的move=1

求A的根的时候，每次递归root就把上一层更新的根节点的move值累加了

#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#define inf 0x3f3f3f3f
#define ll __int64
using namespace std;

int r[10005],vis[10005],move[10005];

int root(int a)
{
    if(r[a]==a) return a;
    int tmp=r[a];
    r[a]=root(r[a]);
    move[a]+=move[tmp];
    return r[a];
}

void merge(int a,int b)
{
    int ra,rb;
    ra=root(a);
    rb=root(b);
    if(ra==rb) return ;
    move[ra]=1;//第一次合并 赋为1 这个不能在root里递加哦
    r[ra]=rb;
    vis[rb]+=vis[ra];
}

int main()
{
    int t,n,q,a,b,i,cnt=0;
    char s[10];
    scanf("%d",&t);
    while(t--)
    {
        cnt++;
        printf("Case %d:\n",cnt);
        scanf("%d%d",&n,&q);
        for(i=0;i<=n;i++)
            r[i]=i,vis[i]=1;
        memset(move,0,sizeof move);
        while(q--)
        {
            scanf("%s",s);
            if(s[0]==‘T‘)
            {
                scanf("%d%d",&a,&b);
                merge(a,b);
            }
            else
            {
                scanf("%d",&a);
                int tmp=root(a);
                printf("%d %d %d\n",tmp,vis[tmp],move[a]);
            }
        }
    }
    return 0;
}

hdu3635 Dragon Balls,布布扣,bubuko.com

hdu3635 Dragon Balls

原文：http://blog.csdn.net/u011032846/article/details/20940123