首页 > 代码库 > hdu2818(带权并查集)
hdu2818(带权并查集)
题目连接:http://acm.hdu.edu.cn/showproblem.php?pid=2818
还是不熟练。。。
1 #include<cstdio> 2 #include<cstring> 3 const int maxn=30005; 4 int f[maxn],under[maxn],sum[maxn]; 5 6 void init() 7 { 8 for(int i=0;i<=maxn;i++) 9 { 10 f[i]=i; 11 sum[i]=1; 12 under[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 under[x]+=under[t]; 23 } 24 return f[x]; 25 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 under[pa]=sum[pb]; 35 sum[pb]+=sum[pa]; 36 f[pa]=pb; 37 } 38 } 39 40 int main() 41 { 42 char c[5]; 43 int n,x,y; 44 while(scanf("%d",&n)!=EOF) 45 { 46 init(); 47 for(int i=0;i<n;i++) 48 { 49 scanf("%s",c); 50 if(c[0]==‘M‘) 51 { 52 scanf("%d%d",&x,&y); 53 uni(x,y); 54 } 55 else 56 { 57 scanf("%d",&x); 58 gf(x); 59 printf("%d\n",under[x]); 60 } 61 } 62 } 63 return 0; 64 }
hdu2818(带权并查集)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。