[置顶] 杭电3635-Dragon Balls-并查集之路径压缩

By | 08月24日
Advertisement

Problem Description

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.
[置顶]

        杭电3635-Dragon Balls-并查集之路径压缩

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.
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 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.
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)

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.

Sample Input

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

Sample Output

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

传送门

解题思路:

该题大意是有n个龙珠在n个城市,现分别执行以下两种操作:“T”表示将x龙珠移到y城市,而“Q”表示输出x所在城市,该城市的龙珠总数,以及该龙珠移动次数。

此题就是一道纯并查集的简单应用,但却涉及到了路径压缩的知识。下面先来介绍一下路径压缩。

关于路径压缩,维基百科解释如下:

“路径压缩”,是一种在执行“查找”时扁平化树结构的方法。关键在于在路径上的每个节点都可以直接连接到根上;他们都有同样
的表示方法。为了达到这样的效果,Find递归地经过树,改变每一个节点的引用到根节点。得到的树将更加扁平,为以后直接或者
间接引用节点的操作加速
那什么是扁平化呢?
[置顶]

        杭电3635-Dragon Balls-并查集之路径压缩

其实就是减少了树的深度,使得下一次查找更加方便。

下面是迭代版路径压缩:

int findRoot(int x)
{
            int tempRoot;
            int root = x;
            while(root != parent[root])
                        root = parent[root];

            while(x != root)
            {
                        tempRoot = parent[x];
                        parent[x] = root;
                        x = tempRoot;
            }
            return root;
}

但有时候有些题却不能用迭代版,于是有下面的递归版:

    int find_root(int x)
    {
        int root;
        root = x;
        while( root != father[root])
            root = father[root];
        return root;
    }

再回到问题上来,前面2个很好实现,最后移动次数有点麻烦,将要转移的龙珠所在城市的根节点的转移次数加1,等到路径压缩时,子节点自己移动次数加上根节点移动次数,就是节点总共移动次数。

可能有点绕,稍微从文字角度上说一下。

比如说要把城市i的龙珠转移到j,先让i所在树的根(这里的根其实就是i城市本来有的龙珠也就是i号龙珠)的转移次数为1(因为第一次转移)

然后从开始向根节点路径压缩。假设从i到顶点一共有四层(也就是说,目前i城市里边有4颗龙珠,根节点龙珠是i号)

根结点为1号龙珠(根节点),然后第二层2号龙珠,第三层3号龙珠,第四层4号龙珠.那么,第一层路径压缩过程中进入第二层,然后第三层,然后第四层,第四层也就是根,找到根结点,返回第三层,第三层+上第四层的转移次数,然后返回第二层,第二层转移次数加上第三层转移次数,返回第一层,第一层转移次数加上第二层转移次数,同时,在这个过程中也把下面3层的结点的父节点直接更新为和根结点,也就是1相连。

下附代码:

#include <iostream>
#include <cstdio>

using namespace std;

const int maxn = 10010;

int city[maxn];//表示i号城市有几个球
int parent[maxn];//表示i球在哪个城市
int transport[maxn];//表示i球被转移了几次
int t,n,q;

void makeset()
{
      for(int i=0;i<=n;i++)
      {
            city[i] = 1;
            parent[i] = i;
            transport[i] = 0;
      }
}

int findRoot(int x)
{
      if(x == parent[x])
            return x;
      int tempRoot = parent[x];
      parent[x] = findRoot(parent[x]);//路径压缩
      transport[x] += transport[tempRoot];
      return parent[x];
}

void Union(int x,int y)
{
      int xRoot = findRoot(x);
      int yRoot = findRoot(y);
      if(xRoot != yRoot)
      {
            parent[xRoot] = yRoot;
            transport[xRoot] = 1;
            city[yRoot] += city[xRoot];
            city[xRoot] = 0;
      }
}

int main()
{
      scanf("%d",&t);
      int num = 1;
      while(t--)
      {
            scanf("%d %d",&n,&q);
            printf("Case %d:\n",num++);
            makeset();
            char str[10];
            while(q--)
            {
                  scanf("%s",str);
                  if(str[0] == 'T')
                  {
                        int x,y;
                        scanf("%d %d",&x,&y);
                        Union(x,y);
                  }
                  else if(str[0] == 'Q')
                  {
                        int x;
                        scanf("%d",&x);
                        int k =findRoot(x);
                        printf("%d %d %d\n",k,city[k],transport[x]);
                  }
            }
      }
      return 0;
}

Similar Posts:

  • hdu 3635 Dragon Balls(并查集)

    Dragon Balls Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2909 Accepted Submission(s): 1125 Problem Description Five hundred years later, the number of dragon balls will increase unexpectedly,

  • HDU 3635 Dragon Balls(并查集:路径压缩)

    HDU 3635 Dragon Balls(并查集:路径压缩) http://acm.hdu.edu.cn/showproblem.php?pid=3635 题意: 这里有N个龙珠,每个龙珠初始时都在本身的城市(第i个龙珠在第i个城市),然后要你回答对应的询问. 输入:首先是一个T(0< T <= 100),表示由T个实例.对于每个实例,第一行是N and Q (2 < N <= 10000 , 2 < Q <= 10000),表示接下来有Q个询问.然后对应每个询问是下

  • Dragon Balls(并查集)

    Dragon Balls Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K (Java/Other) Total Submission(s) : 9 Accepted Submission(s) : 5 Problem Description Five hundred years later, the number of dragon balls will increase unexpectedly, so it'

  • hud Step5.1.6 3635 Dragon Balls(并查集)

    Step5.1.6 3635 Dragon Balls Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 456 AcceptedSubmission(s): 195 Problem Description Five hundred years later, the number ofdragon balls will increase unex

  • hdu 3635 Dragon Balls 【基础带权并查集】

    Dragon Balls Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 3461 Accepted Submission(s): 1348 Problem Description Five hundred years later, the number of dragon balls will increase unexpectedly,

  • hdu 3635 Dragon Balls 龙珠 带权并查集

    每次移动都是一个群龙珠移动到另一群龙珠所在的城市里面.所以这两个城市之间都不会空. 用并查集表示,每一个祖先节点的序号和他们所在城市的序号相同. 无论路径如何压缩,子结点的移动次数=父节点的移动次数+1; Dragon Balls Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 4943    Accepted Submission(s

  • HDU 3635 Dragon Balls 七龙珠 Union Find算法

    孙悟空要寻找七龙珠,这回是七龙珠的增强版了,因为这些龙珠会衍生,最后不止七颗龙珠了. 悟空带着布玛的龙珠雷达探测器出发了,却发现布玛的龙珠雷达探测器的程序太垃圾了,所以找到我们这些ACM高手为龙珠雷达探测器写个程序,要求可以显示某颗龙珠所在的城市的位置,该龙珠所在的城市共有多少颗龙珠,龙珠移动过的次数. 布玛是个有钱人啊,写个程序我要价5百万,不算过分吧.因为本程序需要用到Union Find(并查集)算法,而且最困难的部分是如何压缩路径,不压缩路径自然容易做到,要压缩路径可以使得程序加快很多,

  • [置顶] 【思考题】字串的连接最长路径查找

    目标需求: 输入n个字符串,如果一个字符串末尾有k个字符与另一个字符串头k个字符相同,则这两个字符串可以连接,比如 abcdef cdefgh这两个字符串可以连接成abcdefgh 从这n个字符串中,寻找可以连接成最长字串的方案. //样例输入: //ABCC ABCD BCCE BCDE CCEF BCCE CCEG CEGF //样例输出: //ABCCEGF 思路: 1.对所有字符串做编号1,2,3,4,5,.......: 2.对编号进行全排列: 3.对一次排列结果按排列编号进行连接,并

  • [置顶] 【面试题】面试题合集一

    1.[阿里]"村长"带着4对父子参加"爸爸去哪儿"第三季第二站某村庄的拍摄.村里为了保护小孩不被拐走有个千年的规矩,那就是吃饭的时候小孩左右只能是其他小孩或者自己的父母.那么4对父子在圆桌上共有几种坐法.(旋转一下,每个人面的的方向变更后算是一种新的坐法). A 144 B 240 C 288 D 480 E 576 F 960 [推测-->不一定正确] 左图中,先选择两个父亲放置在父亲团边界,剩下两个父亲和村长可以随意组合排列,而南方的两孩子位置可换,然后父

  • [置顶] 可自动扩展的高可用Swarm集群EdgeScaler的搭建

    项目简介 应用场景 集群架构 组件描述 集群搭建 环境准备 Swarm工作节点搭建 Swarm管理节点搭建 ConfdHAProxy节点搭建 小结 项目简介 随着虚拟化和容器技术的日趋成熟,Docker越来越受到人们的关注,目前Docker已经发展到1.10版本,并且已经可以在生产环境大规模部署.本文介绍EdgeScaler集群系统,使用Swarm+Docker+Registrator+Etcd+Confd+HAProxy搭建了一个可自动可扩展的docker集群. 应用场景 EdgeScaler

Tags: