強連結成分分解のリンク集
強連結成分分解について、参考になる記事や資料をまとめました。
強連結成分分解(SCC)は、有向グラフの頂点を「互いに行き来できる頂点どうし」のグループ(強連結成分)に分けることです。各成分を 1 つの頂点に縮約すると、閉路のない有向グラフ(DAG)になるので、その上でトポロジカル順に DP などができるようになります。DFS を 2 回行う Kosaraju 法や、DFS を 1 回行い lowlink を使う Tarjan 法で、 で求められます。2-SAT もこれを使って解きます。
成分を並べる順序には注意が必要です。AtCoder Library(ACL)の scc_graph::scc() は成分をトポロジカル順(辺の始点側の成分が先)に返しますが、Tarjan 法をそのまま書くと成分は逆トポロジカル順に見つかります。自分で書いたり他のライブラリを使ったりするときは、どちらの順かを確かめてください。また、1 頂点だけの成分は、自己ループがなければ閉路を含みません。DFS を再帰で書くと、頂点数が多いときに再帰が深くなりすぎることがあります。
まず読むもの
Section titled “まず読むもの”- 強連結成分分解の意味とアルゴリズム(高校数学の美しい物語)
- 定義と、元のグラフで DFS をして帰りがけ順に番号を付け、辺を逆向きにしたグラフで番号の大きい頂点から DFS する手順(Kosaraju 法)を、図と具体例で説明しています。正しさの証明もありますが概略で、途中の補題は省略されています。コードはありません。
- AtCoder Library Practice Contest G - SCC(けんちょんの競プロ精進記録)
- 強連結成分分解とは何か、縮約すると DAG になる理由を図で説明し、ACL を使うコードと、DFS を 2 回行う自前の C++ 実装(縮約した DAG も作る)を載せています。
- 強連結成分(SCC)(technical-note)
- Kosaraju 法の手順を、DFS で番号を付けるところから成分を 1 つずつ取り出すところまで、図で 1 ステップずつ追っています。「上流・下流」のたとえで正しさを直感的に説明していて、厳密な証明やコードはありません。
縮約した DAG と 2-SAT
Section titled “縮約した DAG と 2-SAT”- 競技プログラミングにおける有向グラフに関する問題まとめ(はまやんはまやんはまやん)
- トポロジカルソート、強連結成分分解、DAG の最小パス被覆、区間に辺を張る方法など、有向グラフの手法と、それを使う問題をまとめています。説明は短く、解説は外部の記事へのリンクが中心です。2017 年の記事です。
- 2-SAT(cp-algorithms、英語)
- 節 を と の 2 本の辺にした含意グラフを作り、 と が同じ成分にあるかで判定し、成分のトポロジカル順の番号から割り当てを決める方法を、証明つきで説明しています。C++ の実装もあります。
- 実装の最後の使用例
example_usageにあるvector<bool>(True, False, True)は C++ として正しくないので、そこはそのまま写さないでください。
AtCoder Algorithm Lectures
Section titled “AtCoder Algorithm Lectures”強連結成分分解そのものを扱う講座はまだありません。関連する講座として、次のものがあります。
- グラフ理論用語集
- 5 章で強連結成分と強連結グラフを、9 章で DAG とトポロジカルソートを定義しています。DAG であることは、すべての強連結成分が 1 頂点からなりループを持たないことと同値だ、とも書かれています。
- トーナメント
- 5 章で、トーナメント(どの 2 頂点の間にもちょうど 1 本の向きつきの辺がある有向グラフ)では強連結成分が一列に並び、強連結成分分解が各頂点の入次数だけから決まることを示しています。
- scc(AtCoder Library のドキュメント)
scc_graphにadd_edgeで辺を追加し、scc()で成分ごとの頂点のリストを受け取ります。成分はトポロジカル順に並び、成分の中の頂点の順序は決まっていません。計算量は です。
- two_sat(AtCoder Library のドキュメント)
- 節 を
add_clauseで追加し、satisfiable()で判定、answer()で割り当てを受け取ります。内部では強連結成分分解を使っています。
- 節 を
- Strongly Connected Components (強連結成分分解)(Luzhiled’s Library)
- Tarjan 法の C++ 実装で、各頂点の成分番号
comp(トポロジカル順に振り直してある)、成分ごとの頂点group、縮約した DAGdagが得られます。DFS は再帰を使わずに書かれています。
- Tarjan 法の C++ 実装で、各頂点の成分番号
百科事典・英語の資料
Section titled “百科事典・英語の資料”- 強連結成分(日本語版 Wikipedia)
- 定義、縮約すると DAG になること、Kosaraju 法・Tarjan 法・経路ベースの方法、並列化向けの方法を短く紹介しています。擬似コードはなく、各方法の説明は数文です。
- Strongly connected component(英語版 Wikipedia)
- 日本語版と同じ範囲に加えて、2-SAT や Dulmage–Mendelsohn 分解への応用にも触れています。
- Tarjan’s strongly connected components algorithm(英語版 Wikipedia)
- Tarjan 法の擬似コードと計算量の説明があります。成分が逆トポロジカル順に出力されることや、lowlink の更新方法に原論文と違う変種があることも書かれています。
- 強連結成分分解(Kyopro Encyclopedia of Algorithms)
- 定義、計算量、縮約すると DAG になることを短くまとめた辞典の項目です。DFS を 2 回行う方法と lowlink を使う方法の参考として、上の高校数学の美しい物語の記事と ACL が挙げられています。
- Strongly Connected Components and Condensation Graph(cp-algorithms)
- Kosaraju 法と Tarjan 法の両方を、証明と C++ 実装つきで説明しています。縮約したグラフの作り方と、Kosaraju 法では成分がトポロジカル順、Tarjan 法では逆トポロジカル順に得られることも書かれています。
- 実装は再帰の DFS で、縮約したグラフには多重辺が残ります。
- Strongly Connected Components(USACO Guide)
- Kosaraju 法と Tarjan 法の実装と、後半に 2-SAT の節があります。SCC と 2-SAT それぞれの問題の一覧もあります。
- Library Checker - Strongly Connected Components:強連結成分分解をして、成分をトポロジカル順に出力します。ライブラリの verify 用です。
- AtCoder Library Practice Contest G - SCC:上と同じ問題で、ACL の
scc_graphの練習用です。 - AtCoder Library Practice Contest H - Two SAT:旗を と のどちらに置くかを変数にした 2-SAT です。
- Library Checker - 2 Sat:DIMACS 形式で与えられる 2-SAT を解きます。ライブラリの verify 用です。
- 競プロ典型 90 問 021 - Come Back in One Piece(★5):互いに行き来できる頂点の組の数を、各成分の大きさから求めます。
- ABC245 F - Endless Walk:無限に移動を続けられる頂点を数えます。2 頂点以上の成分に到達できるかを考えます。
- ABC296 E - Transition Game: のグラフで閉路に乗っている頂点を数えます。自己ループのある 1 頂点の成分も閉路です。
- ABC357 E - Reachability in Functional Graph:各頂点から到達できる頂点の数を、縮約した DAG の上の DP で求められます。
- TDPC R - グラフ:2 本の経路で塗れる頂点数の最大値を、縮約した DAG の上の DP で求めます。
- ABC374 G - Only One Product Name:縮約した DAG で最小パス被覆を求め、二部マッチングに帰着させます(公式解説)。
- ABC210 F - Coprime Solitaire:カードの表裏を変数にした 2-SAT で、補助変数を使って節の数を減らします(公式解説)。
- ABC277 Ex - Constrained Sums:「」を変数にすると、和の条件が 2-SAT の節で書けます(公式解説)。
このブログの記事
Section titled “このブログの記事”- ABC478 E - lt and le
- 不等式の条件を辺にしたグラフを強連結成分分解し、
<の辺の両端が同じ成分にあれば No、なければ成分のトポロジカル順の番号をそのまま答えにしています。本番では嘘解法で通してしまった話も書いています。
- 不等式の条件を辺にしたグラフを強連結成分分解し、
- ShareOJ Programming Contest vol.1 E - Solicitation of Murder
- 外から入る辺のない成分に生存者が必ず残ることを示し、成分ごとに独立に数えて掛け合わせています。