King Slime (AOJ 2382)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2382

問題

W,Hのフィールドに居るN体のスライムを蹴って、一箇所に集めたい。スライムは一度蹴ると端か他のスライムに当たるまで止まらない。また蹴ったスライムが他のスライムに当たると2体は合体し、その場に留まる。全てのスライムを合体させるのに何回蹴る必要があるか。
2<=N<=40,000
1<=W,H<=100,000

解法

x座標もしくはy座標が同一のスライムを連結成分と見なす。連結成分にいるスライム全てを合体させるにはその連結成分の頂点数-1かかる。別の連結成分のスライムを合体させるには一旦壁まで蹴れば良い。ただし連結成分が2個以上あり、壁に隣接しているスライムがいる場合は答えが1減る。