コンテンツにスキップ

強連結成分分解

タグ「強連結成分分解」の記事 3 件

強連結成分分解のリンク集

強連結成分分解について、参考になる記事や資料をまとめました。

強連結成分分解(SCC)は、有向グラフの頂点を「互いに行き来できる頂点どうし」のグループ(強連結成分)に分けることです。各成分を 1 つの頂点に縮約すると、閉路のない有向グラフ(DAG)になるので、その上でトポロジカル順に DP などができるようになります。DFS を 2 回行う Kosaraju 法や、DFS を 1 回行い lowlink を使う Tarjan 法で、O(N+M)O(N + M) で求められます。2-SAT もこれを使って解きます。

成分を並べる順序には注意が必要です。AtCoder Library(ACL)の scc_graph::scc() は成分をトポロジカル順(辺の始点側の成分が先)に返しますが、Tarjan 法をそのまま書くと成分は逆トポロジカル順に見つかります。自分で書いたり他のライブラリを使ったりするときは、どちらの順かを確かめてください。また、1 頂点だけの成分は、自己ループがなければ閉路を含みません。DFS を再帰で書くと、頂点数が多いときに再帰が深くなりすぎることがあります。

  • 強連結成分分解の意味とアルゴリズム(高校数学の美しい物語)
    • 定義と、元のグラフで DFS をして帰りがけ順に番号を付け、辺を逆向きにしたグラフで番号の大きい頂点から DFS する手順(Kosaraju 法)を、図と具体例で説明しています。正しさの証明もありますが概略で、途中の補題は省略されています。コードはありません。
  • AtCoder Library Practice Contest G - SCC(けんちょんの競プロ精進記録)
    • 強連結成分分解とは何か、縮約すると DAG になる理由を図で説明し、ACL を使うコードと、DFS を 2 回行う自前の C++ 実装(縮約した DAG も作る)を載せています。
  • 強連結成分(SCC)(technical-note)
    • Kosaraju 法の手順を、DFS で番号を付けるところから成分を 1 つずつ取り出すところまで、図で 1 ステップずつ追っています。「上流・下流」のたとえで正しさを直感的に説明していて、厳密な証明やコードはありません。
  • 競技プログラミングにおける有向グラフに関する問題まとめ(はまやんはまやんはまやん)
    • トポロジカルソート、強連結成分分解、DAG の最小パス被覆、区間に辺を張る方法など、有向グラフの手法と、それを使う問題をまとめています。説明は短く、解説は外部の記事へのリンクが中心です。2017 年の記事です。
  • 2-SAT(cp-algorithms、英語)
    • 節 (a∨b)(a \lor b) を ¬a⇒b\lnot a \Rightarrow b と ¬b⇒a\lnot b \Rightarrow a の 2 本の辺にした含意グラフを作り、xx と ¬x\lnot x が同じ成分にあるかで判定し、成分のトポロジカル順の番号から割り当てを決める方法を、証明つきで説明しています。C++ の実装もあります。
    • 実装の最後の使用例 example_usage にある vector<bool>(True, False, True) は C++ として正しくないので、そこはそのまま写さないでください。

強連結成分分解そのものを扱う講座はまだありません。関連する講座として、次のものがあります。

  • グラフ理論用語集
    • 5 章で強連結成分と強連結グラフを、9 章で DAG とトポロジカルソートを定義しています。DAG であることは、すべての強連結成分が 1 頂点からなりループを持たないことと同値だ、とも書かれています。
  • トーナメント
    • 5 章で、トーナメント(どの 2 頂点の間にもちょうど 1 本の向きつきの辺がある有向グラフ)では強連結成分が一列に並び、強連結成分分解が各頂点の入次数だけから決まることを示しています。
  • scc(AtCoder Library のドキュメント)
    • scc_graph に add_edge で辺を追加し、scc() で成分ごとの頂点のリストを受け取ります。成分はトポロジカル順に並び、成分の中の頂点の順序は決まっていません。計算量は O(n+m)O(n + m) です。
  • two_sat(AtCoder Library のドキュメント)
    • 節 (xi=f)∨(xj=g)(x_i = f) \lor (x_j = g) を add_clause で追加し、satisfiable() で判定、answer() で割り当てを受け取ります。内部では強連結成分分解を使っています。
  • Strongly Connected Components (強連結成分分解)(Luzhiled’s Library)
    • Tarjan 法の C++ 実装で、各頂点の成分番号 comp(トポロジカル順に振り直してある)、成分ごとの頂点 group、縮約した DAG dag が得られます。DFS は再帰を使わずに書かれています。
  • 強連結成分(日本語版 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 それぞれの問題の一覧もあります。
  • ABC478 E - lt and le
    • 不等式の条件を辺にしたグラフを強連結成分分解し、< の辺の両端が同じ成分にあれば No、なければ成分のトポロジカル順の番号をそのまま答えにしています。本番では嘘解法で通してしまった話も書いています。
  • ShareOJ Programming Contest vol.1 E - Solicitation of Murder
    • 外から入る辺のない成分に生存者が必ず残ることを示し、成分ごとに独立に数えて掛け合わせています。

ShareOJ Programming Contest vol.1 E - Solicitation of Murder

NN 頂点 MM 辺の有向グラフが与えられます。辺 a→ba \to b は「囚人 aa は囚人 bb に殺意を持っている」ことを表します。「生存している a,ba, b で辺 a→ba \to b があるものを選び、bb を殺す」という操作を好きな回数行ったあと、生存している囚人の集合としてありうるものの個数を 998244353998244353 で割った余りを求める問題です。

テストケースは TT 個あり、NN の総和と MM の総和はそれぞれ 2×1052 \times 10^5 以下です。

グラフを強連結成分分解します。外から入ってくる辺がない強連結成分(入次数 00 の成分)を、ここでは始点成分と呼びます。

生存者の集合 SS がありうるのは、すべての始点成分に SS の頂点が 1 つ以上あるときで、そのときに限ります。

必要性. 始点成分 CC の頂点を殺せるのは、CC の頂点だけです。CC の頂点が全員殺されたとすると、CC の中で最後に殺された頂点を殺した頂点は CC の中にいて、そのあとに殺されています。これは最後であることに反します。よって、CC には生存者が残ります。

十分性. どの頂点も、どこかの始点成分から到達できます。強連結成分の中では互いに到達できるので、すべての始点成分に SS の頂点があれば、すべての頂点が SS のどれかの頂点から到達できます。そこで、SS からの距離 d(v)d(v) を考え、SS にない頂点を d(v)d(v) が大きい順に殺します。d(v)=t≥1d(v) = t \ge 1 の頂点 vv には、d(u)=t−1d(u) = t - 1 で辺 u→vu \to v がある頂点 uu があります。uu は SS の頂点か、vv よりあとに殺す頂点なので、vv を殺すときにはまだ生きています。したがって、vv を殺せます。

条件は成分ごとに独立です。

  • 始点成分 CC では、空でない部分集合ならどれでもよいので 2∣C∣−12^{|C|} - 1 通りです。
  • それ以外の成分 CC では、制限がないので 2∣C∣2^{|C|} 通りです。

これらの積が答えです。

C++
#include "shogo-library/base/all"
#include "shogo-library/graph/graph.hpp"
#include "shogo-library/graph/graph_util.hpp"
#include "shogo-library/math/modint.hpp"
using mint = modint998244353;
void solve() {
LL(N, M);
Graph<> g(N);
rep(M) {
LL(a, b);
a--, b--;
g.add_directed_edge(a, b);
}
vl dp(N);
auto tmp = strongly_connected_components(g);
mint ans = 1;
for (const auto &f : tmp) {
ll x = 0;
for (ll u : f) {
x |= dp[u];
}
ans *= mint(2).pow(f.size()) - !x;
for (ll u : f) {
for (ll v : g[u])
dp[v] = 1;
}
}
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
LL(T);
rep(T)
solve();
}

strongly_connected_components は強連結成分をトポロジカル順に返します。dp[v] は「すでに処理した成分から vv に入る辺がある」ことを表すフラグです。成分 f を見る時点で、f に外から入る辺はすべて前の成分から来ているので、x が 00 なら f は始点成分です。成分の中の辺で立つフラグは、x を求めたあとに立てています。

使用ライブラリ:cpp_include@397a51d

ABC478 E - lt and le

11 以上 NN 以下の整数からなる長さ NN の列 AA で、QQ 個の条件「Au≤AvA_u \le A_v」または「Au<AvA_u < A_v」をすべて満たすものがあるかを判定し、あれば 1 つ出力する問題です(N,Q≤2×105N, Q \le 2 \times 10^5)。

条件 Au≤AvA_u \le A_v、Au<AvA_u < A_v のどちらも、頂点 uu から vv への辺だと思ってグラフを作り、強連結成分(SCC)分解します。

  • 同じ SCC の中の頂点は、辺をたどって一周できるので、Au≤⋯≤AuA_u \le \cdots \le A_u となり、すべて同じ値でなければなりません。したがって、<< の辺の両端が同じ SCC にあれば No です。
  • そうでなければ、SCC をトポロジカル順に並べたときの番号(11 始まり)をそのまま AA にすれば条件をすべて満たします。異なる SCC 間の辺は必ず番号が増える向きなので << も ≤\le も満たし、同じ SCC 内の辺はすべて ≤\le なので等しい値で満たします。番号は NN 以下です。

ACL の scc_graph::scc() は成分をトポロジカル順に返すので、その添字をそのまま使えます。計算量は O(N+Q)O(N + Q) です。

本番では次の方針で提出し、AC しました。

  1. ≤\le の辺だけで SCC 分解し、同じ成分を「等しい値になるグループ」として DSU でまとめる
  2. すべての辺で SCC 分解し、異なるグループが同じ SCC に入ったら No
  3. そうでなければ SCC の番号を出力する

ところが、同じグループ(等しくなることが決まった頂点どうし)の間に << の辺がある場合を見落としていました。<< の辺で弾いていたのは u=vu = v のときだけです。たとえば

2 3
0 1 2
0 2 1
1 1 2

は A1=A2A_1 = A_2 が必要なのに A1<A2A_1 < A_2 も要求されているので答えは No ですが、本番のコードは Yes と 1 1 を出力してしまいます。テストケースにこの形がなかったため通ってしまったようです。

上の解法のように、<< の辺の両端が同じ SCC にあるかを最後に確かめれば、この場合も正しく No になります(修正版で AC を確認しました)。そもそも DSU も 2 回目の SCC も要らず、SCC 1 回で十分でした。

C++(修正版・AC)
#include "atcoder/scc"
#include "sh-library/base/all"
void solve() {
LL(N, Q);
VAL(TUV, Q, 3);
atcoder::scc_graph g(N);
for (auto &[t, u, v] : TUV) {
u--, v--;
g.add_edge(u, v);
}
auto scc = g.scc();
vl ans(N);
rep(i, scc.size()) {
for (ll x : scc[i])
ans[x] = i + 1;
}
for (auto [t, u, v] : TUV) {
if (t == 1 and ans[u] == ans[v]) {
No;
}
}
print("Yes");
print(ans);
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

使用ライブラリ:cpp_include@6c2f83f

C++(本番の提出・嘘解法)
#include "atcoder/dsu"
#include "atcoder/scc"
#include "sh-library/base/all"
void solve() {
LL(N, Q);
VAL(TUV, Q, 3);
atcoder::dsu h(N);
{
atcoder::scc_graph g0(N);
for (auto &[t, u, v] : TUV) {
u--, v--;
if (t == 0) {
g0.add_edge(u, v);
} else {
if (u == v) {
print("No");
return;
}
}
}
auto tmp = g0.scc();
for (auto &x : tmp) {
rep(i, 1, x.size()) {
h.merge(x[0], x[i]);
}
}
}
{
atcoder::scc_graph g(N);
for (auto &[t, u, v] : TUV) {
if (t == 0 && h.same(u, v)) {
g.add_edge(v, u);
}
g.add_edge(u, v);
}
auto tmp = g.scc();
for (auto &x : tmp) {
rep(i, 1, x.size()) {
if (h.same(x[0], x[i]))
continue;
print("No");
return;
}
}
vl ans(N);
rep(i, tmp.size()) {
for (ll a : tmp[i]) {
ans[a] = i + 1;
}
}
print("Yes");
print(ans);
}
}
int main() {
std::cin.tie(nullptr);
std::ios_base::sync_with_stdio(false);
solve();
}

使用ライブラリ:cpp_include@6c2f83f