HDU-3635-Dragon Balls

ACM模版

描述

题解

让悟空学学并查集就搞定了~~~

这里的两种操作需要说一下，翻译起来好难。

T A B把A龙珠所在城市的所有龙珠都移到B龙珠所在城市；
Q A查询A龙珠相关信息，分别是A龙珠现在所在城市、该城市的龙珠数目、A转移到该城市所移动的次数。

代码

#include <iostream>
#include <map>

using namespace std;

const int MAXN = 1e4 + 10;

int pre[MAXN];
int sum[MAXN];
int mov[MAXN];
int total;

int find(int x)
{
    if (x != pre[x])
    {
        int temp = pre[x];
        pre[x] = find(pre[x]);
        mov[x] += mov[temp];    // 父亲移动的次数会叠加到儿子身上
    }
    return pre[x];
}

void join(int x, int y)
{
    int fx = find(x);
    int fy = find(y);

    if (fx != fy)
    {
        pre[fx] = fy;
        sum[fy] += sum[fx];
        mov[fx]++;      // 根节点移动次数++
        sum[fx] = 0;    // 移走后剩余0
    }
}

int main()
{
    int T;
    cin >> T;
    int key = 1;
    int N, Q;
    int A, B;
    char order[2];

    while (T--)
    {
        printf("Case %d:\n", key++);

        scanf("%d%d", &N, &Q);
        for (int i = 0; i <= N; i++)
        {
            pre[i] = i;
            sum[i] = 1;
            mov[i] = 0;
        }

        while (Q--)
        {
            scanf("%s", order);
            if (order[0] == 'T')
            {
                scanf("%d%d", &A, &B);
                join(A, B);
            }
            else
            {
                scanf("%d", &A);
                int res = find(A);
                printf("%d %d %d\n", res, sum[res], mov[A]);
            }
        }
    }

    return 0;
}