首页 > 代码库 > hdu 3635
hdu 3635
http://acm.hdu.edu.cn/showproblem.php?pid=3635
1-n个城市,对应放着编号1-n的龙珠。
两种操作
T A B 把编号A的龙珠所在城市内的全部龙珠放到有编号B的龙珠的城市内
Q A 查询编号A的龙珠的信息,输出三个数,A所在城市,A所在城市龙珠数目,A转移到该城市所用次数
思路:对球进行并查集维护,sum[a]表示a点移动到目前根的次数,每次合并的时候把A球根节点的sum设为1,这是并查集一个经典的操作,转移次数问题解决。A球所属城市的龙珠数目单开一个数组记录一下即可。所属城市就是根节点编号(这个点的球没有被合并过,所以球编号等于城市编号)
#include <iostream>#include <cstdio>#include <cstring>#include <map>#include <algorithm>#include <queue>#include <cmath>#include <stack>#include <set>using namespace std;int fa[10005],sum[10005],cnt[10005];int find(int x){ if(fa[x]!=x){ int pre=fa[x]; fa[x]=find(fa[x]); sum[x]+=sum[pre]; } return fa[x];}int main(){ int T; scanf("%d",&T); for(int cas=1;cas<=T;cas++){ int n,q; scanf("%d%d",&n,&q); for(int i=0;i<=n;i++){ fa[i]=i; cnt[i]=1; } memset(sum,0,sizeof(sum)); printf("Case %d:\n",cas); while(q--){ char op[5]; scanf("%s",op); if(op[0]==‘T‘){ int a,b; scanf("%d%d",&a,&b); int pa=find(a); int pb=find(b); if(pa!=pb){ fa[pa]=pb; cnt[pb]+=cnt[pa]; sum[pa]=1; } } else{ int a; scanf("%d",&a); int rt=find(a); printf("%d %d %d\n",rt,cnt[rt],sum[a]); } } } return 0;}
hdu 3635
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。