hdu 3635 Dragon Balls(并查集)

时间:2022-03-03 16:12:10

题意:

N个城市,每个城市有一个龙珠。

两个操作:

1.T A B:A城市的所有龙珠转移到B城市。

2.Q A:输出第A颗龙珠所在的城市,这个城市里所有的龙珠个数,第A颗龙珠总共到目前为止被转移了多少次。

思路:

前两个好求,第三个求转移的次数只要把它到根的路径上的值加起来就行了

看代码

代码:

int N,Q;
int fa[10005], ballNum[10005], moveTime[10005]; int findFa(int x){
if(fa[x]==x)
return fa[x];
int t=findFa(fa[x]);
moveTime[x]+=moveTime[fa[x]];
ballNum[x]=ballNum[t];
return fa[x]=t;
} int main(){ int T;
cin>>T;
rep(t,1,T){
scanf("%d%d",&N,&Q); rep(i,1,N){
fa[i]=i;
ballNum[i]=1;
moveTime[i]=0;
} printf("Case %d:\n",t);
while(Q--){
char ope[5];
int A,B;
scanf("%s",ope);
if(ope[0]=='T'){
scanf("%d%d",&A,&B);
int fA=findFa(A);
int fB=findFa(B);
if(fA!=fB){
ballNum[fB]+=ballNum[fA];
moveTime[fA]++;
fa[fA]=fB;
}
}else{
scanf("%d",&A);
findFa(A);
printf("%d %d %d\n",fa[A],ballNum[A],moveTime[A]);
}
}
} return 0;
}

hdu 3635 Dragon Balls(并查集)的更多相关文章

  1. hdu 3635 Dragon Balls(并查集)

    Dragon Balls Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  2. hdu 3635 Dragon Balls(并查集应用)

    Problem Description Five hundred years later, the number of dragon balls will increase unexpectedly, ...

  3. hdu 3635 Dragon Balls (带权并查集)

    Dragon Balls Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  4. HDU 3635 Dragon Balls(超级经典的带权并查集!!!新手入门)

    Dragon Balls Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Tota ...

  5. hdu 3635 Dragon Balls(加权并查集)2010 ACM-ICPC Multi-University Training Contest(19)

    这道题说,在很久很久以前,有一个故事.故事的名字叫龙珠.后来,龙珠不知道出了什么问题,从7个变成了n个. 在悟空所在的国家里有n个城市,每个城市有1个龙珠,第i个城市有第i个龙珠. 然后,每经过一段时 ...

  6. hdu 3635 Dragon Balls (MFSet)

    Problem - 3635 切切水题,并查集. 记录当前根树的结点个数,记录每个结点相对根结点的转移次数.1y~ 代码如下: #include <cstdio> #include &lt ...

  7. hdu 3635 Dragon Balls

    Dragon Balls Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others) Tot ...

  8. HDU 3635 Dragon Balls(带权并查集)

    http://acm.hdu.edu.cn/showproblem.php?pid=3635 题意: 有n颗龙珠和n座城市,一开始第i颗龙珠就位于第i座城市,现在有2种操作,第一种操作是将x龙珠所在城 ...

  9. HDU 1811 拓扑排序 并查集

    有n个成绩,给出m个分数间的相对大小关系,问是否合法,矛盾,不完全,其中即矛盾即不完全输出矛盾的. 相对大小的关系可以看成是一个指向的条件,如此一来很容易想到拓扑模型进行拓扑排序,每次检查当前入度为0 ...

随机推荐

  1. My97Datepicker 去掉 &OpenCurlyDoubleQuote;不合法格式或超期范围”自动纠错限制

    官网上,纠错有以下三种,如日期格式不对,或超期,则必须纠错过后,才能继续操作, 但有时,可能允许出错,需要把纠错功能去掉,则可以设置errDealMode = 3,这种模式是官网说没有的, 但能够去掉 ...

  2. &lbrack;Swift&rsqb;LeetCode552&period; 学生出勤记录 II &vert; Student Attendance Record II

    Given a positive integer n, return the number of all possible attendance records with length n, whic ...

  3. python网络爬虫笔记(二)

    一.函数调用的默认设置 1.def enroll(name,grnder,age=4,city='Shanghai'): print (''name:',name) print (''gender', ...

  4. rsync详细配置

    1 说在前面的话 rsync官方网站: https://www.samba.org/ftp/rsync/rsync.html rsync是可以实现增量备份的工具.配合任务计划,rsync能实现定时或间 ...

  5. maven win 安装 与 IntelliJ IDEA 配置Maven【2018-11-14最新最有姿势攻略】

    [博客园cnblogs笔者m-yb原创,转载请加本文博客链接,笔者github: https://github.com/mayangbo666,公众号aandb7,QQ群927113708] http ...

  6. CAN2&period;0A 和CAN2&period;0B

    CAN2.0A 和CAN2.0B 原创 2015年08月03日 16:03:08 3969 CAN2.0A 是CAN协议的PART A部分,此部分定义了11bit的标识区 .CAN2.0B 是CAN协 ...

  7. JavaScript document对象

    1.document对象是window对象的子对象,可直接使用,多用于获取HTML页面元素 2.document对象属性 a) alinkColor活动链接颜色 b) linkColor文本链接颜色 ...

  8. 继续bzoj

    我应该可以打卡下班了,回来继续bzoj

  9. 【智能算法】迭代局部搜索(Iterated Local Search&comma; ILS)详解

    迭代局部搜索(Iterated Local Search, ILS) 源代码下载请关注微信公众号[程序猿声],在后台回复:[ILS],不包括[]即可下载. 00 目录 局部搜索算法 简单局部搜索 迭代 ...

  10. gitlab 把或名改成IP

    [root@GitLab assets]# cat /etc/gitlab/gitlab.rb # Change the external_url to the address your users ...