首页 > 代码库 > hdu 3635 Dragon Balls
hdu 3635 Dragon Balls
http://acm.hdu.edu.cn/showproblem.php?pid=3635
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 20000 5 using namespace std; 6 7 int f[maxn]; 8 int add[maxn]; 9 int move1[maxn]; 10 int n,Q,a1,b1; 11 char ch; 12 13 int find1(int x) 14 { 15 if(x==f[x]) return x; 16 int f1=find1(f[x]); 17 move1[x]+=move1[f[x]]; 18 f[x]=f1; 19 return f[x]; 20 } 21 22 void union1(int a,int b) 23 { 24 int fa=find1(a); 25 int fb=find1(b); 26 if(fa!=fb) 27 { 28 add[fb]+=add[fa]; 29 move1[fa]=1; 30 f[fa]=fb; 31 } 32 } 33 34 void inti() 35 { 36 for(int i=1; i<=n; i++) 37 { 38 f[i]=i; 39 add[i]=1; 40 } 41 } 42 43 int main() 44 { 45 int T; 46 scanf("%d",&T); 47 for(int ca=1; ca<=T; ca++) 48 { 49 scanf("%d%d",&n,&Q); 50 inti(); 51 getchar(); 52 memset(move1,0,sizeof(move1)); 53 printf("Case %d:\n",ca); 54 for(int i=1; i<=Q; i++) 55 { 56 scanf("%c %d",&ch,&a1); 57 if(ch==‘T‘) 58 { 59 scanf("%d",&b1); 60 union1(a1,b1); 61 } 62 else if(ch==‘Q‘) 63 { 64 int c1=find1(a1); 65 printf("%d %d %d\n",c1,add[c1],move1[a1]); 66 } 67 getchar(); 68 } 69 } 70 return 0; 71 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。