首页 > 代码库 > 带权并查集(个人模版)
带权并查集(个人模版)
带权并查集:
1 #include<stdio.h> 2 #include<string.h> 3 using namespace std; 4 int f[1000010]; 5 int sum[1000010]; 6 int find(int x) 7 { 8 if(x!=f[x]) 9 { 10 int pre=f[x];//pre是x的一个父节点。 11 f[x]=find(f[x]);//递归找祖先。 12 sum[x]+=sum[pre]; 13 } 14 return f[x]; 15 } 16 int main() 17 { 18 int n; 19 while(~scanf("%d",&n)) 20 { 21 for(int i=0;i<=n;i++) 22 { 23 f[i]=i; 24 sum[i]=0; 25 } 26 int op; 27 while(n--) 28 { 29 scanf("%d",&op); 30 if(op==1) 31 { 32 int x,y,val; 33 scanf("%d%d%d",&x,&y,&val); 34 int X=find(x); 35 int Y=find(y); 36 if(X!=Y) 37 { 38 sum[Y]=val-sum[y]+sum[x]; 39 f[Y]=X; 40 } 41 } 42 else 43 { 44 int x,y; 45 scanf("%d%d",&x,&y); 46 int X=find(x); 47 int Y=find(y); 48 if(X!=Y) 49 { 50 printf("?\n"); 51 } 52 else 53 { 54 printf("%d\n",sum[y]-sum[x]); 55 } 56 } 57 } 58 } 59 }
带权并查集(个人模版)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。