N

Wesley13
• 阅读 508
有标号为1到n的n个龙珠,分别放在对应标号为1到n的n个城市里。
下面有两种操作:
T A B表示把A龙珠所在城市的所有龙珠都转移到B龙珠所在的城市中
Q A 表示查询A,需要知道A龙珠现在所在的城市,A所在的城市有几颗龙珠,A转移到这个城市移动了多少次,分别输出3个整数,表示上述信息。 

前两个用普通并查集就能算出来,移动次数不好维护;

如果我们不进行路径压缩,那么查询点的深度即是移动的次数,因为每移动一次父节点就下降一层,深度+1;

但不路径压缩的话就会超时,所以我们要把点的深度记录下来;;

#include <cstdio>
#include <algorithm>
#include <iostream>

using namespace std;
int  ans[100000] ,ansn[100000] ,pre[100000];

void init( int x){
    for( int i = 0 ; i<=x ;i++){
        pre[i] = i;
        ans[i] = 0;
        ansn[i] = 1;
    }
}

int  find( int a){
   /* int r=a;           //刚开始这样记录深度ans[a],但是这样不对,这样只是路径压缩一次ans[n]++,但实际上一次可能压缩很多层,所以应该是加上上一层的压缩层数
    while( pre[a]!=a){
        a=pre[a];
     }
     int t;
     while( pre[r]!=a){
         ans[r]++;
         t= pre[r];
         pre[r] =a;
         r=t;
     }*/
     if( a == pre[a] )return a;
     else{
        int tmp= pre[a];
        pre[a] = find( pre[a]);
        ans[a] += ans[tmp];
     }
     return pre[a];
}

int add( int a ,int b){
     int x=find(a);
     int y=find(b);
     if( x != y){
         pre[x] = y;
         ans[x] = 1;
         ansn[y] += ansn[x];
         ansn[x] =0;
     }
}

int main( ){
     int ks=0, T;
     scanf("%d",&T);
     while( T--){
         printf("Case %d:\n",++ks);
        int n,m;
        scanf("%d%d" ,&n ,&m);
        init( n);
        while( m--){
             char op[10];
             int a,b;
             scanf("%s",op);
             if( op[0] == 'T'){
                scanf("%d%d" ,&a,&b);
                add( a,b);
             }
             if( op[0] == 'Q'){
                 scanf("%d" ,&a);
                 int b=find(a);
                     printf("%d %d %d\n" ,b ,ansn[b] ,ans[a]);
             }
        }
     }
    return 0;
}
点赞
收藏
评论区
推荐文章
DaLongggggg DaLongggggg
3年前
python刷题-序列求和
问题描述求123...n的值。输入格式输入包括一个整数n。输出格式输出一行,包括一个整数,表示123...n的值。样例输入4样例输出10样例输入100说明:有一些试题会给出多组样例输入输出以帮助你更好的做题。一般在提交之前所有这些样例都需要测试通过才行,但这不代表这几组样例数据都正确了你的程序就是完全正确的,潜在的错误可能仍然导致你的得分较低
DaLongggggg DaLongggggg
3年前
python刷题-字母图形
问题描述利用字母可以组成一些美丽的图形,下面给出了一个例子:ABCDEFGBABCDEFCBABCDEDCBABCDEDCBABC这是一个5行7列的图形,请找出这个图形的规律,并输出一个n行m列的图形。输入格式输入一行,包含两个整数n和m,分别表示你要输出的图形的行数的列数。输出格式输出n行,每个m个字符,为你的图形。样例输入57样例输
先知 先知
3年前
C 语言代码大全
1两个数组的合并题目描述已知数组a中有m个按升序排列的元素,数组b中有n个按降序排列的元素,编程将a与b中的所有元素按降序存入数组c中。输入输入有两行,第一行首先是一个正整数m,然后是m个整数;第二行首先是一个正整数n,然后是n个整数,m,n均小于等于1000000。输出输出合并后的mn个整数,数据之间用空格隔开。输出占一行。样例输入4
DaLongggggg DaLongggggg
3年前
python刷题-最大最小公倍数
问题描述已知一个正整数N,问从1~N中任选出三个数,他们的最小公倍数最大可以为多少。输入格式输入一个正整数N。输出格式输出一个整数,表示你找到的最小公倍数。样例输入9样例输出504数据规模与约定1<N<106。Nint(input())Min1ifN<2:print(N)elifN%2
DaLongggggg DaLongggggg
3年前
python-阶乘计算
问题描述  输入一个正整数n,输出n的值。  其中n123…n。算法描述  n可能很大,而计算机能表示的整数范围有限,需要使用高精度计算的方法。使用一个数组A来表示一个大整数a,A0表示a的个位,A1表示a的十位,依次类推。  将a乘以一个整数k变为将数组A的每一个元素都乘以k,请注意处理相应的进位。  首先将a设为1,然后乘2,
DaLongggggg DaLongggggg
3年前
python刷题-进制转换
十六进制转八进制问题描述  给定n个十六进制正整数,输出它们对应的八进制数。输入格式  输入的第一行为一个正整数n(1<n<10)。  接下来n行,每行一个由0~9、大写字母A~F组成的字符串,表示要转换的十六进制正整数,每个十六进制数长度不超过100000。输出格式  输出n行,每行为输入对应的八进制正整数。  【注意】  输入的十六进制数不会有
DaLongggggg DaLongggggg
3年前
python刷题-数列特征
问题描述给出n个数,找出这n个数的最大值,最小值,和。输入格式第一行为整数n,表示数的个数。第二行有n个数,为给定的n个数,每个数的绝对值都小于10000。输出格式输出三行,每行一个整数。第一行表示这些数中的最大值,第二行表示这些数中的最小值,第三行表示这些数的和。样例输入513245样例输出5211数据规模与约定1<n<10000。
Wesley13 Wesley13
3年前
1187.年龄最小的三个职工
题目描述:职工有职工号,姓名,年龄.输入n个职工的信息,找出3个年龄最小的职工打印出来。  输入:输入第一行包括1个整数N,1<N<30,代表输入数据的个数。接下来的N行有N个职工的信息:包括职工号(整数),姓名(字符串,长度不超过10),年龄(1<age<100)。输出:可能有多
Stella981 Stella981
3年前
FZU2150 Fire Game
题目:_两个熊孩子在n\m的平地上放火玩,表示草,两个熊孩子分别选一个格子点火,火可以向上向下向左向右在有草的格子蔓延,点火的地方时间为0,蔓延至下一格的时间依次加一。求烧完所有的草需要的最少时间。如不能烧完输出1。_输入:_第一行,输入一个T,表示有T组测试数据。每组数据由一个n,m分别表示行列_1
Stella981 Stella981
3年前
Bzoj4899 记忆的轮廓
B.记忆的轮廓题目描述通往贤者之塔的路上,有许多的危机。我们可以把这个地形看做是一颗树,根节点编号为1,目标节点编号为n,其中1n的简单路径上,编号依次递增,在\1,n\中,一共有n个节点。我们把编号在\1,n\的叫做正确节点,\n1,m\的叫做错误节点。一个叶子,如果是正确节点则为正确叶子,否则称