UnKoder #01 : XOR Graph

幸いすんなり解法が思いつけた。
https://www.hackerrank.com/contests/unkoder-01/challenges/xor-graph

問題

初期状態として、N頂点M辺からなるグラフが与えられる。

ここに何本か辺を足し、全体を連結グラフにしたい。
その際、X番の頂点とY番の頂点の間に辺を追加するとX xor Yのコストがかかる。

全体を連結グラフにするための最小コストを求めよ。

解法

クラスカル法の応用で最小全域木を作る。

まず各頂点pに対し、(p xor 1)の頂点が非連結ならコストを1払ってそれらを結ぶ。
次は、各頂点pに対し、(p xor 2)頂点が非連結ならコストを1払ってそれらを結ぶ。

以後同様に2^iのコストの辺を順々に追加していけば良い。
なぜ2の累乗以外の辺を考慮する必要がないか、だが、たとえばpとp xor 6の頂点が非連結な場合、コストを6払ってこれらを結ぶ前に、pと(p xor 2)、(p xor 2)と(p xor 6)=(p xor 2 xor 4)を結んだ方が同じ総コスト6でも(p xor 2)にも追加で辺を張れるので得である。
よって2の累乗以外のコストの辺は考慮しなくてよい。

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<100050> uf;

int N,M;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>x>>y;
		uf(x,y);
	}
	ll ret=0;
	FOR(y,20) {
		FOR(i,N) {
			x=i ^ (1<<y);
			if(x<N && uf[i]!=uf[x]) uf(i,x), ret+=1<<y;
		}
	}
	cout<<ret<<endl;
}

まとめ

面白い問題でした。