首页 > 代码库 > hdu 3635 Dragon Balls (带权并查集)
hdu 3635 Dragon Balls (带权并查集)
题目:
链接:点击打开链接
题意:
把编号为1~n的龙珠放到编号为1~n的城市中去。现在有T和Q两种操作:
T:A B 把A龙珠所在城市的所有龙珠转移到B城市中。
Q:A 表示查询A龙珠的一些信息:X(A所在的城市),Y(A所在城市龙珠的数目),Z(A转移到该城市被移动的次数)。
思路:
代码:
#include <iostream> #include <cstdio> #include <cstring> using namespace std; const int N = 10010; struct node{ int parent; int son; int TransNum; }p[N]; int n,q; int a,b,c,ans; char ch; int findset(int x) { int temp; if(x == p[x].parent) return x; else { temp = p[x].parent; p[x].parent = findset(p[x].parent); p[x].TransNum += p[temp].TransNum; } return p[x].parent; } void mergeset(int x,int y) { int fx = findset(x); int fy = findset(y); if(fx != fy) { p[fx].parent = fy; p[fx].TransNum++; p[fy].son += p[fx].son; p[fx].son = 0; } } void init() { for(int i=1; i<=n; i++) { p[i].parent = i; p[i].son = 1; p[i].TransNum = 0; } } int main() { //freopen("input.txt","r",stdin); int t; int kase = 0; cin>>t; while(t--) { scanf("%d%d",&n,&q); getchar(); init(); printf("Case %d:\n",++kase); for(int i=0; i<q; i++) { scanf("%c",&ch); getchar(); if(ch == 'T') { scanf("%d%d",&a,&b); mergeset(a,b); } else { scanf("%d",&c); ans = findset(c); printf("%d %d %d\n",ans,p[ans].son,p[c].TransNum); } getchar(); } } return 0; }
----------------------------------------------
战斗,从不退缩;奋斗,永不停歇~~~~~~~~
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。