首页 > 代码库 > hdu3635
hdu3635
题目链接:HDU - 3635
1 #include<cstdio> 2 #include<cstring> 3 const int maxn=10010; 4 int f[maxn],ct[maxn],trans[maxn]; 5 int n,m; 6 void init() 7 { 8 for(int i=0;i<=n;i++) 9 { 10 f[i]=i; 11 ct[i]=1; 12 trans[i]=0; 13 } 14 } 15 16 int gf(int x) 17 { 18 if(x!=f[x]) 19 { 20 int t=f[x]; 21 f[x]=gf(t); 22 trans[x]+=trans[t]; 23 24 } 25 return f[x]; 26 } 27 28 void uni(int a,int b) 29 { 30 int pa=gf(a); 31 int pb=gf(b); 32 if(pa!=pb) 33 { 34 f[pa]=pb; 35 trans[pa]++; 36 ct[pb]+=ct[pa]; 37 } 38 } 39 int main() 40 { 41 int t; 42 char s[5]; 43 int u,v; 44 int cas=1; 45 scanf("%d",&t); 46 while(t--) 47 { 48 printf("Case %d:\n",cas++); 49 scanf("%d%d",&n,&m); 50 init(); 51 for(int i=0;i<m;i++) 52 { 53 scanf("%s",s); 54 if(s[0]==‘T‘) 55 { 56 scanf("%d%d",&u,&v); 57 uni(u,v); 58 } 59 else 60 { 61 scanf("%d",&u); 62 gf(u); 63 printf("%d %d %d\n",f[u],ct[f[u]],trans[u]); 64 } 65 } 66 } 67 }
hdu3635
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。