hdu Dragon Balls

这题是一道简单的并查集的运用。龙珠所在的城市、该城市龙珠数目都是很简单的问题，稍微麻烦一点的就是龙珠被移动的次数，因为每一次要移动的是一个城市中所有的龙珠，所以每次移动该城市中所有龙珠的移动次数都要加一。

一开始用二维数组存放每个城市中龙珠的编号，MLE了。接着改用map嵌套queue，却TLE了，不过这个是意料之中的。后来再想想，发现自己有点蠢，其实每个龙珠移动的次数等于它移动的次数加上它根节点移动的次数，这样问题就变得简单了。这就类似于从根节点到当前结点的一个权值累积过程，这时候的Find（）函数用递归写会使整个程序变得简单明了。

#include"iostream"

#include"stdio.h"

#include"string.h"

#include"string"

#include"algorithm"

#include"cmath"

#include"vector"

#include"queue"

#include"map"

using namespace std;

const int mx=;

int N,Q;

int fa[mx];

int move_times[mx];

int ball_count[mx];

void Set()

{

    int i;

    for(i=;i<=N;i++)

    {

        fa[i]=i;

        move_times[i]=;

        ball_count[i]=;

    }

}

int Find(int x)

{

    if(x==fa[x]) return x;

    int t=fa[x];

    fa[x]=Find(fa[x]);

    move_times[x]+=move_times[t];

    return fa[x];

}

void Union(int x,int y)

{

    int fx=Find(x);

    int fy=Find(y);

    if(fx!=fy)

    {

        move_times[fx]++;

        ball_count[fy]+=ball_count[fx];

        //这个可以去掉，因为不可能在像龙珠个数为零的城市移动

        ball_count[fx]=;

        fa[fx]=fy;

    }

}

void IO()

{

    int T,i,m,n,icase=;;

    char ope;

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d%d",&N,&Q);

        Set();

        printf("Case %d:\n",icase++);

        while(Q--)

        {

            getchar();

            scanf("%c",&ope);

            switch(ope)

            {

            case 'T':

                scanf("%d%d",&m,&n);

                Union(m,n);

                break;

            case 'Q':

                scanf("%d",&m);

                int fm=Find(m);

                printf("%d% d% d\n",fm,ball_count[fm],move_times[m]);

                break;

            }

        }

    }

}

int main()

{

   // freopen("E:\\in.txt","r",stdin);

    IO();

    return ;

}