Union-Find木について＜実践編＞

　またまた日が空きました.......。

　前回は「Union-Find木」の内容を紹介しました。

today-f.hatenablog.jp

　今回は実際にAtCoderでUnion-Find木を用いて問題を解いてみたいと思います。

問題

　AtCoder ABC120のD問題。（この問題で初めてUnion-Find木に出会いました。）

atcoder.jp

解法

　個の島と本の橋があって、この橋が順番に崩落した際のその時その時の”行き来できない島と島の組み合わせ”＝”不便さ”を求める問題ですね。

　これは時間の流れを逆にして考えるのだそうです。

　どの島同士もつながっていない状態から入力の逆順に橋をつなげていくことで、Union-Find木の「グループの結合」という特徴を利用することができるのです。

　まずはじめの状態においてどの島も孤島ですから、”不便さ”は 。

　次に回目に橋を架けるとき、架ける島と島がもう別の橋から行き来できる場合は不便さは変わらないので、回目に橋を架けた際の不便さと同じです。

　回目で初めて2つの島が行き来できるようになる場合は、それぞれの島が属するグループの総数の組み合わせですから求める不便さは、

(回目のときの不便さ)ー(島１のグループのサイズ)＊(島２のグループのサイズ)

となります。

実装
　
　C++でのコードは以下のようになりました。

#include<iostream>
#include<vector>
#define REP(i,n) for(int i=0;i<(n);++i)
using namespace std;
typedef long long   llong;
typedef vector<int> vi;

struct UnionFind{
	std::vector<int> par;
        /*xの親はpar[x]. 
        もしx自身が親ならpar[x]<0で,-par[x]がその集合のサイズ.*/
	int cnt;//グループの数.
	
	UnionFind(int n):par(n,-1),cnt(n){}//コンストラクタ.
	
	void reset(int n){par.assign(n,-1),cnt=n;}
	int root(int x){return (par[x]<0)?x:par[x]=root(par[x]);}
        /*再帰.*/
	int size(int x){return -par[root(x)];}
	bool same(int x,int y){return root(x)==root(y);}
	bool unite(int x,int y){
		x=root(x), y=root(y);
		if(x==y) return false;//do nothing.
		if(size(x)<size(y)) swap(x,y);//merge technique.
		par[x]+=par[y];
		par[y]=x;
		cnt--;
		return true;
	}
};

int main(){
	int n,m;
	cin>>n>>m;
	
	vi a(m),b(m);
	REP(i,m){
		cin>>a[i]>>b[i];
		a[i]--, b[i]--;
	}
	
	UnionFind is(n);
	vector<llong> ans(m);
	ans[m-1]=(llong)n*(n-1)/2;//nC2.
	for(int i=m-1;i>=1;--i){
		if(is.same(a[i],b[i])) ans[i-1]=ans[i];
		else{
                ans[i-1]=ans[i]-(llong)is.size(a[i])*is.size(b[i]);
                }
		is.unite(a[i],b[i]);
	}
	
	REP(i,m) cout<<ans[i]<<endl;
}

　以上がUnion-Findを使った例でした。理解すると構造体の仕組みに感動して、使うのがなかなか面白かったです。

#寒くなってきた夜