并查集— Dragon Balls

转自：https://www.cnblogs.com/yinbiao/p/9464390.html

题目： http://www.fjutacm.com/Contest.jsp?cid=870#P3

这题真的搞得我头痛，可能是我对并查集还没有深刻的理解吧

Five hundred years later, the number of dragon balls will increase unexpectedly, so it's too difficult for Monkey King(WuKong) to gather all of the dragon balls together.

五百年后，龙珠的数量会出乎意料地增加，所以悟空很难把所有的龙珠聚集在一起。

His country has N cities and there are exactly N dragon balls in the world. At first, for the ith dragon ball, the sacred dragon will puts it in the ith city. Through long years, some cities' dragon ball(s) would be transported to other cities. To save physical strength WuKong plans to take Flying Nimbus Cloud, a magical flying cloud to gather dragon balls.

他的国家有N个城市，世界上正好有N个龙珠。首先，为了第i个龙珠，神圣的龙会把它放在第i个城市。经过漫长的岁月，一些城市的龙珠会被运送到其他城市。为了节省体力，悟空计划乘飞天云，一种神奇的飞天云来收集龙珠。

Every time WuKong will collect the information of one dragon ball, he will ask you the information of that ball. You must tell him which city the ball is located and how many dragon balls are there in that city, you also need to tell him how many times the ball has been transported so far.

每次悟空收集一个龙珠的信息，他都会问你那个龙珠的信息。你必须告诉他球在哪个城市，在那个城市有多少个龙珠，你还需要告诉他球已经被运送了多少次。

Input

The first line of the input is a single positive integer T(0 < T <= 100).
For each case, the first line contains two integers: N and Q (2 < N <= 10000 , 2 < Q <= 10000).
Each of the following Q lines contains either a fact or a question as the follow format:

输入的第一行是一个正整数T(0 < T <= 100)。

对于每种情况，第一行包含两个整数:N和Q (2 < N <= 10000, 2 < Q <= 10000)。

下列Q行中的每一行都包含一个事实或一个问题，其格式如下:

T A B : All the dragon balls which are in the same city with A have been transported to the city the Bth ball in. You can assume that the two cities are different.

T A B 表示：所有和A在同一个城市的所有龙珠都被运到了B球所在的城市。你可以假设这两个城市是不同的（PS：注意是所有）
Q A : WuKong want to know X (the id of the city Ath ball is in), Y (the count of balls in Xth city) and Z (the tranporting times of the Ath ball). (1 <= A, B <= N)

Q A 表示：悟空想知道X(第 A 个球所在城市的 id )， Y( 第X个城中球的数量 )，Z( 第 A 个球被运送的次数 )。 (1 <= A, B <= N)

Output

For each test case, output the test case number formated as sample output. Then for each query, output a line with three integers X Y Z saparated by a blank space.

对于每个测试用例，输出作为示例输出的测试用例编号。然后，对于每个查询，输出一行三个由空格分隔的整数X Y Z。

2
3 3
T 1 2
T 3 2
Q 2
3 4
T 1 2
Q 1
T 1 3
Q 1

Case 1:
2 3 0
Case 2:
2 2 1
3 3 2

我在网上看了好几篇博客，好像都觉的这题挺简单的，都没有什么解释。可惜这题我卡在移动次数卡了好久，那个球的移动次数真的有点不理解，怪我太笨 ((ノ*T_T*)

一，输出的问题，注意理解，测试用例编号是在事实和询问之前就打印出来了

二，询问的第二个，之前做过，不想多说，就是求某个集合的元素数量，直接在构造一个数组，在链接两个点的时候同时递加，最后保存在根节点就好了

三，询问的第一个，说之前先讲一下，T A B，这是一个集合的整体移动的，这也是这题为什么用并查集的原因，一整个集合指向一个点（要移动的目的城市），这不就是并查集压缩路径之后的样子吗？

我们只要在连接两个点的时候，注意让目的城市成为父节点，就可以构造出要移动的集合了。所以，最后，根节点是有特殊含义的，其实也就是 find (x) = 第 x个球所在城市的 id,也就是第一个询问了

四，询问的第三个

说之前，我想先讲一下，find 函数

int find(int x)   // 可将递归分为 两个过程
{
    int a = x;
    while (p[x] != x)   // 搜索的过程
        x = p[x];
    while (a != x)     // 回溯的过程
    {
        int t = p[a];
        p[a] = x;
        a = t;
    }
    return x;
}
int Find(int x)
{
    if (p[x] != x)
        p[x] = Find(p[x]);
    return p[x];
}

find 函数可以要实现两个功能　　① 找到根结点　　② 压缩路径

函数实现可以有两种方法　　① 循环　　② 递归

就是在做这个时，我第一次想到，可以将递归分为两部分　　① 调用自己之前的代码　　② 调用自己之后的代码

愚以为，第一部分是搜索实现找到根结点的功能；第二部分是回溯实现压缩路径的功能

我觉得这个应该可以推广到所有递归（然而现在我递归做到的题目不够多，不知道有没有例外 ( ｡ớ ₃ờ) ）

想法一，之前打算构造一个 mov 数组，在 join 函数连接两个点的时候，让移动的那个城市 id ，mov[id]++,

后发现当别的点移动时，是会带动集合的点也跟着移动的，这样子，其他点就没有记录到

想法二，还是在 join 函数，连接两个点之前，构造一个函数，让所有指向这个点的点的mov++, 结果超时了

超时代码：

void fun(int x)
{
    for (int i = 0; i <= n; i++)
    {
        if (p[i] == x)
            mov[i]++;
    }
}
void join(int x, int y)
{
    x = find(x), y = find(y);
    if (x == y)
        return;
    fun(x);    // 
     p[x] = y;
     num[y] += num[x];
}

想法三，在想法一的基础上，加一个函数，在查询时，直接让 x 的所有父节点的mov[] 加起来，结果 wa, 　原因：忘记被压缩路径了，找不回去了

错误代码：

int move(int x)
{
    int sum = 0, a = x;
    while (p[x] != x)
    {
        sum += mov[x];
        x = p[x];
    }
    sum += mov[x];
    return sum;
}
void join(int x, int y)
{
    x = find(x), y = find(y);
    if (x == y)
        return;
     p[x] = y;
     num[y] += num[x];
     mov[x]++;
}
if (str[0] == 'Q')
{
    scanf("%d", &x);
    int k = find(x);
    printf("%d %d %d
", k, num[k], mov[x]);
}

所以，我就直接百度了，๑乛◡乛๑ (●´∀｀●)

是基于我对想法一，利用 find 的回溯对其他点进行处理

说实话，由于没解释我这个代码直接看了一天，才理解，现在已然是在熬夜了 (＠Ｕ▽Ｕ＠)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#define N 10005
int p[N], num[N], mov[N];
int n, m;
int find(int x)
{
    if (p[x] != x)
    {
        int t = p[x];
        p[x] = find(p[x]);
        mov[x] += mov[t];  // 回溯时 从根节点加回去的，但是，是 子节点+=父节点
    }
    return p[x];
}
void join(int x, int y)
{
    x = find(x), y = find(y);
    if (x == y)
        return;
     p[x] = y;
     num[y] += num[x];
     mov[x]++;
}
int main(void)
{
    int t; scanf("%d", &t);
    int ci = 0;
    while (t--)
    {
        scanf("%d%d", &n, &m);
        for (int i = 0; i <= n; i++)
        {
            p[i] = i;
            num[i] = 1;
            mov[i] = 0;
        }

        printf("Case %d:
", ++ci);
        char str[10];
        while (m--)
        {
            scanf("%s", str);
            int x, y;
            if (str[0] == 'T')
            {
                scanf("%d%d", &x, &y);
                join(x, y);
            }
            if (str[0] == 'Q')
            {
                scanf("%d", &x);
                int k = find(x);
                printf("%d %d %d
", k, num[k], mov[k]);
            }
        }
    }

    system("pause");
    return 0;
}

还是画图比较好理解：

若现在假设 T 3 5 且看图

那么， join 之后，会变成什么呢？且看：

注意到了吗，压缩路径是由延迟的，不是你添加了一个点，他就马上压缩，而是在你连接一个新的点之后，

确定了根结点，才压缩的，（这也是我做这题时才发现的）

而且，在回溯累加 mov[] 数组的时候，是没有把根节点算上去的，这样子他算的就只有原来那个集合了

不信，接着看。

接下来有两种情况：

① 询问 3 或 4 或 5 或 1，分别得到 mov[3]+mov[1],mov[2]+mov[1],mov[4]+mov[1],mov[1]，

然后查询之后路径就被压缩了，若是第二次查询 3 或 4 或 5 或 1，只会得到 mov[3]，mov[4]，mov[5]，mov[1]

② 或者不询问，接着移动那么，就会这样：

T 3 6

join 之后就会：(抱歉，这里有点小错误，由于只是 find(3),find(6),所以，被压缩的应该之后，3->1->5, 而 find(6) 深度为1 就没有压缩了，应该是第二张图，这是之后再来看才发现的 )

正确图片：

递归过程：

x=3; -> t=1 -> p[x]=find(p[x])=5 -> mox[x]+=mov[t] 即 mov[3]+=mov[1]=2; 结束

周而复始。

我能说什么，简直天秀，真的，凡是能想出用递归解决问题都是大佬啊，而且这个直接利用原来就有的递归，简直了ヾ(o◕∀◕)ﾉ

最后总结一下吧，总体思路应该是和我对的想法3 一样，只是我因为被压缩路径了，不知道如何处理，而这个是利用递归，在回溯时候累加，

因为路径上的每个点都是与前面路径有关，所以每个点必须把前面所有点累加起来，这个用递归就挺简单，但若用循环的话就很麻烦

谢谢观看！！！

========== ======= ======= ====== ====== ===== ==== === == =

尘曲七堇年

凡心所向，素履所往; 生如逆旅，一苇以航。

稣合于言，安之若素; 自言自语，无喜无悲。

凡心所向，素履所往; 生如逆旅，一苇以航。

三月桃花，四月欢唱; 两人一马，明日故乡。

流浪陌路，暖然绯凉; 写意人生，相识一场。

不关此世，不负己心; 我自倾杯，且君随意。