Cube Stacking（并查集加递归） POJ - 1988


有n个箱子，初始时每个箱子单独为一列；
接下来有p行输入，M, x, y 或者 C, x；
对于M,x,y：表示将x箱子所在的一列箱子搬到y所在的一列箱子上；
对于C,x：表示求箱子x下面有多少个箱子

思路：开一个num数组，表示第i个箱子所在的集合共有多少个箱子。

开一个step数组，表示第i个箱子在所在的集合中排第几。

开一个pre数组，普通并查集。

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include<set>
#include 
#include
#include    
#include
#include
#include
using namespace std;
#define inf 1<<30
#define eps 1e-7
#define LD long double
#define LL long long
#define maxn 100000005    
int pre[100009] = {};
int num[100009] = {};
int step[100009] = {};
int rootsearch(int root)
{
    if (root == pre[root])
    {
        return pre[root];
    }
    int temp = pre[root];   //保存前面的根
    pre[root] = rootsearch(pre[root]); //递归先改变后面的
    step[root] += step[temp];  //到根的距离
    return pre[root];
}
int main()
{
    for (int i = 1; i <= 30009; i++)//预处理一下
    {
        pre[i] = i;
        num[i] = 1;
        step[i] = 0;
    }
    int n, x, y, a, b;
    scanf("%d", &n);
    getchar();
    for (int i = 1; i <= n; i++)
    {
        char flag;
        scanf("%c", &flag);
        if (flag == 'M')
        {
            scanf("%d%d", &x, &y);
            a = rootsearch(x);
            b = rootsearch(y);
            if (a!=b)//根不同
            {
                pre[b] = a;                //把b集合合并到a
                step[b] = num[a];         //b的排名就是a集合的数量
                num[a] = num[a] + num[b];//集合a的数量就是a集合与b集合之和
            }
        }
        else if (flag == 'C')
        {
            scanf("%d", &x);
            printf("%d\n",num[rootsearch(x)]-step[x]-1 );//答案就是x的根所代表的集合的数量-x的排名-x本身
        }
        getchar();
    }
}
ACM

相关

acm讲解

「acmhdu - 6314」Matrix

第十三届河南省ACM-ICPC游记

ACM模板

Hyperf 接入阿里云ACM应用配置管理中心

[ACM] BFS & 双端BFS & A* & 双边BFS

计算几何 / Geometry（ACM-Template 2.0）

ACM入门方式

Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书

如何写好一篇高质量的IEEE/ACM Transaction级别的计算机科学论文?

ACM- java在acm中的快速读入，多组读入，快速输出模板

ACM - 动态规划 - P1282 多米诺骨牌

标签