Union Findの練習及び、テンプレ
//llとはlong long の略です ll parent[100000],depth[100000] ll init(ll n){ REP(i,n){ parent[i]=i; depth[i]=0; } } ll find(ll x){ if(par[x]==x){return x;} else{return par[x]=find(par[x]);} } void merge(ll x,ll y){ x=find(x);y=find(y); if(x==y){return;} if(depth[x]>depth[y]){ par[y]=x; } else{ par[x]=y; if(depth[x]==depth[y]){ depth[y]++; } } } bool same(ll x,ll y){ if(find(x)==find(y)){ return false; } return true; }
ごめんなさい、復習のために直接打ち込んだので、汚いです。。