読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

東京大学プログラミングコンテスト2012: 森ですか? dynamic connectivity

Euler-tour tree Dynamic Connectivity 要修正

http://utpc2012.contest.atcoder.jp/tasks/utpc2012_03

想定解はこの記事の解法より簡単です。

次の PDF を参考にしました。

https://resources.mpi-inf.mpg.de/departments/d1/teaching/ss12/AdvancedGraphAlgorithms/Slides08.pdf

この PDF すごく分かりやすかったので、多分 PDF 見た方がいいと思います。ということで、細かい処理についてはこの記事では書いてません。

euler-tour tree については僕の記事を参考にするなりなんなり。

pekempey.hatenablog.com

(追記 2016/06/25)
最後に載せたコードに不備がある気がしています。 reconnect 時に連結成分をすべて列挙しているのが計算量を破壊しているはずです。 連結成分列挙に全域木を巡回していて、これは本来使うべきではない辺を大量に使う危険性があります。 修正するには特定のレベルの u が属する全域木に接続していている辺だけを取得する手法が必要です。

200000頂点で 200000 回 link してから 200000 回 cut するランダムケースを作ってみたのですが、大体のケースではそこまで時間がかからなくて、重い O(nlog2 n) という感じです。平均 5sec ぐらいで終わります。

辺削除時にかならず reconnect が呼び出されるというわけではないので、ランダムにやると結構すり抜けるとかもあると思います。今回の問題だと序盤は辺の数が多いので、全域木の辺が削除される確率が低くなって速くなっているとかかもしれません。

記事は放置します。コードは頑張って修正したいです。多分修正困難です。

(追記 2016/06/27)
linked list を駆使することで恐らく O(n log2 n) に修正できました。遅いどうこう以前にメモリ消費が激しくて 256 MB の問題だと MLE すると思います。スピードもそんなに速くありません。

level-i の全域木を表現している二分探索木に linked-list の情報を持たせました。

頂点 v に level-i の辺が接続しているなら、頂点 v に対応する二分探索木のノードを marked にします。そして二分探索木上の順序で marked node のみで構成した linked-list を構成します。

これは二分探索木のノードに、部分木の最左 marked-node と最右 marked-node の情報を持たせることで実現できました。linked-list が変化するタイミングは以下の 4 つです。

  • marked から unmarked に変更する操作
  • unmarked から marked に変更する操作
  • 二分探索木の merge
  • 二分探索木の split

unmarked から marked に変更する操作を行うときに、挿入する前後の marked ノードを見つける作業が必要になりますが、これは部分木の最左 marked-node と最右 marked-node の情報があれば根に登りながら見つけることができます。

他の 3 つは割と自明な処理で実現できます。

解法

辺の追加だけなら union-find が使える。グラフが木の場合は euler-tour tree や link-cut tree が使える。しかし今回は一般グラフの追加/削除である。

基本的なアイディアは動的全域木である。連結成分にだけ興味があるので、全域木だけ持つというのは自然なアイディアだろう。

単に全域木だけ持っておくと、全域木に含まれる辺を削除したとき、代わりの辺が存在するかの判定に時間を使ってしまう。

削除処理を高速に行うために、log n 層のレイヤーを用意する。

赤線が全域木の辺で、点線が全域木に使われなかった辺である。バツ印をつけた辺を削除する。

f:id:pekempey:20160625121618p:plain

削除すると全域木が 2 つに分断される。このときサイズの小さい方の全域木 X の辺をすべて上のレイヤーに移動させる。

f:id:pekempey:20160625121710p:plain

削除した辺があったレイヤー上にある X に接続している辺を順に見て、連結成分を繋ぎ直せるかを調べる。もし繋げられなかったら、その辺は上のレイヤーに移動させる。繋げられたら繋いで処理を終える。もしこのレイヤー内に繋ぎ直せる辺が存在しなかったら、ひとつ下のレイヤーに移動して同じことを行う。

f:id:pekempey:20160625121821p:plain

今度は別の辺を削除する。

f:id:pekempey:20160625122115p:plain

さきほどと同様に小さい方の全域木を上のレイヤーに持ち上げる。

f:id:pekempey:20160625122350p:plain

削除した辺は真ん中のレイヤーにあったので、真ん中のレイヤーで u が属する全域木に接続している辺を順に調べていく。繋げたらそれで終了。繋げなかったら上のレイヤーに移動させる。

f:id:pekempey:20160625122237p:plain

このようにしておくと、以下の性質が得られて嬉しい。

(1) 下から i 番目のレイヤーにある全域木のサイズは n/2i 以下。
(2) (1) から分かるようにレイヤー数は log n。
(3) アクセスした辺は必ず上のレイヤーに移動するため、各辺をアクセスする回数は log n 回以下。
(4) 辺 e を削除するとき、再接続する辺の候補は e が属するレイヤーより下に存在。なぜなら上のレイヤーの辺は全域木外への辺を持ち得ないから。

各辺のアクセス回数が log n で抑えられるので、辺全体で見れば O(m log n) 回のアクセスになる。

動的に変化する木の連結判定クエリを大量に処理する必要があるが、全域木は木なので euler-tour tree を使えばいい。

gist.github.com

高速化の余地はありそう。