Hatena::Grouptopcoder

練習帳

 TopCoder(delta2323) / Codeforces(delta) / twitter

2012-05-28

[][] Codeforces Round #120 : E. Counter Attack 01:18 はてなブックマーク -  Codeforces Round #120 : E. Counter Attack - 練習帳

問題文

 問題文

概要

  • 無向グラフが与えられている。
  • このグラフの補グラフを連結成分に分解せよ。
    • グラフG=(V, E)の補グラフG'とは、節がGと同じで、枝は(v, w)∉E(v, w∈V)となるグラフのことである。つまり、もとのグラフの枝の有無を反転させたグラフのこと。
  • 条件:節:n ≦ 5*10**5、枝:m ≦ 10**6

コード

 Practiceでの提出コード(解1):http://codeforces.com/contest/190/submission/1715799

 Practiceでの提出コード(解2):http://codeforces.com/contest/190/submission/1715764

 UnionFindはライブラリから使用:https://github.com/delta2323/algorithm_library

考えた過程

第一歩

一般の場合n**2≫mなので、補グラフはほぼ完全グラフになってしまっています。

nが小さければ、深さ優先探索なりUnion Findなりを使って連結成分分解は簡単にできます。しかし今回はn**2が大きいためにこれらの方法をそのままは使えません。何か飛び道具のようなうまい方法がないかと考えたのですが、結局思いつきませんでした。そこで、ベタに連結成分を計算する方法をうまく工夫して軽くできないかを検討しました。

未決定集合を持つ→失敗

最初に考えたのは、データの持ち方の方での工夫でした:まだどの連結成分に属するかが決まっていない節の集合(未決定集合)を持っておきます。深さ優先探索である節から隣接する節に移動する時には、その節が未決定集合に入っているかを調べ、すでに未決定集合から除かれている場合には移動しない事で枝狩りします。計算量的には問題ないと思うのですが、書き方が下手でRuntime Errorになってしまいました(後述のNG解の1つ目がそれです)。setをiteratorで回しながらstd::set::erase(iteraotr)でその要素を削除しているのでiteratorが無効になっています。

クラスタの数を少なくして連結成分分解

節の数がn個ある完全グラフを深さ優先探索すると、枝の持ち方を工夫しないと計算にO(n**2)だけかかってしまい、これがこの問題のネックになっています。そこで次の方法として、節を予めまとめあげて節の数を減らしてから、深さ優先探索ができないかを考えました。具体的には、二段階に分かれます。第一段階では、節達のうち距離1でつながっているもの達をある程度つなげることでクラスタにまとめ上げ、第二段階でクラスタに対して(ナイーブな)連結成分分解を行います。どちらの段階も最悪O(n**2)だけかかるのですが、今回の(補)グラフが密である事を用いると第一段階では相当な枝狩りが期待でき、第二段階ではクラスタ数が少なくなることが期待できます。実際うまく制限時間に収まりました(解1)。

無効なiteratorを用いないようにしながらtraverseする

Editorialを読んでみると、どうやら節同士をまとめてクラスタにするような事をしなくても、NG解1で考えていた、未決定集合を保持しながら幅優先探索で解答が得られるようです。ただ、setから単純に値を削除してしまうとiteratorが無効になってしまうので、実装の方法を少し工夫が必要でした。その工夫方法がこちらなどで紹介されていました。この方法を用いたのが(解2)です。

NG集