AOJ 2382 King Slime

問題

wxhのグリッド上にn匹のスライムがいる。
1ターンにスライムのうち1匹が、以下のような動きをすることができる。

上下左右の1方向を選び、
壁にぶつかるか、他のスライムがいるマスに入るまで動く。
他のスライムのいるマスに入ると、二つのスライムは合体し、新たなスライムになる。

全てのスライムが合体して１つのスライムになるまでにかかる最小のターン数を求めよ。

制約条件

w, h≦100000
n≦40000

方針

スライムをグラフの頂点と考え、
x座標が同じ同士、y座標が同じ同士のスライムに辺を張る。

すると、グラフが連結な場合、明らかに必要なターン数はn - 1である。
グラフが非連結の場合、連結成分をグリッドの端に寄せてから合体させることになる。

どの端によせるかは4通り試せばよい。
連結成分の中に、その端にすでにいるスライムがいる場合、コストが1減る。
連結成分に、それぞれの端にスライムが初期状態でいるかどうかをフラグとしてもっておいて、合体させるときにフラグを伝播させるようにする。

ソースコード

int n, h, w, x[40000], y[40000];
int p[40000], flag[40000], c;
int root(int x){
	if(x == p[x]) return x;
	return p[x] = root(p[x]);
}
bool use[40000];
vi tate[100000], yoko[100000];

void merge(int a, int b){
	a = root(a); b = root(b);
	if(a == b) return;
	c--;
	p[a] = b;
	flag[b] |= flag[a];
}
int main(){
	cin >> n >> w >> h;
	rep(i, n){
		cin >> x[i] >> y[i];
		if(x[i] == 1) flag[i] |= 1 << 0;
		if(x[i] == w) flag[i] |= 1 << 1;
		if(y[i] == 1) flag[i] |= 1 << 2;
		if(y[i] == h) flag[i] |= 1 << 3;
		p[i] = i;
		
		tate[x[i] - 1].pb(i);
		yoko[y[i] - 1].pb(i);
	}
	c = n;
	rep(i, 100000){
		if(tate[i].size() > 1) rep(j, tate[i].size() - 1) merge(tate[i][j], tate[i][j + 1]);
		if(yoko[i].size() > 1) rep(j, yoko[i].size() - 1) merge(yoko[i][j], yoko[i][j + 1]);
	}
	int ans = inf, cnt[4] = {};
	rep(i, n){
		int r = root(i);
		if(use[r]) continue;
		use[r] = 1;
		rep(j, 4) if(flag[r] & 1 << j) cnt[j]++;
	}
	rep(i, 4) ans = min(ans, n - 1 + c - cnt[i]);
	if(c == 1) ans = n - 1;
	cout << ans << endl;
	
	return 0;
}