Aizu Online Judge(AOJ)の過去問から、その提出コードの解答例です。
・問題 "Weighted Union Find Trees"
https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B
・重み付きUnion Find木
僕が作成、提出したコードは、以下のとおりです。
Aizu Online Judge in C++ #DSL_1_B : Weighted Union Find Trees
/* Aizu Online Judge in C++ #DSL_1_B : Weighted Union Find Trees https://onlinejudge.u-aizu.ac.jp/problems/DSL_1_B 提出コードの解答例 https://neguse-atama.hatenablog.com */ #include<bits/stdc++.h> using namespace std; int n,q; int fat[100000],dis[100000]; int find(int i){ if(fat[i]==i){ return i; } int j=find(fat[i]); dis[i]+=dis[fat[i]]; fat[i]=j; return j; } void f(int x,int y,int z){ int i=find(x); int j=find(y); fat[i]=j; dis[i]=z-dis[x]+dis[y]; } bool tf(int x,int y){ x=find(x); y=find(y); return (x==y); } int f2(int x,int y){ find(x); find(y); return (dis[x]-dis[y]); } int main(void){ cin>>n>>q; for(int i=0;i<n;i++){ fat[i]=i; dis[i]=0; } for(int i=0;i<q;i++){ int k,x,y,z; cin>>k>>x>>y; if(k==0){ cin>>z; f(x,y,z); }else{ if(tf(x,y)){ cout<<f2(x,y)<<endl; }else{ cout<<"?"<<endl; } } } return 0; }
設問の出典は、プログラミング問題のオンライン採点システム「Aizu Online Judge(AOJ)」です。
http://judge.u-aizu.ac.jp/onlinejudge/