こんにちは。 競プロ典型90問を解いていたら強連結成分分解(Strongly Connected Component, SCC)が出てきました。
021 - Come Back in One Piece(★5)
SCC書いたことないので実装してみました。
コード
【クリックして展開】
#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
// https://ei1333.github.io/library/graph/graph-template.hpp
/**
* @brief Graph Template(グラフテンプレート)
*/
template <typename T = int>
struct Edge {
int from, to;
T cost;
int idx;
Edge() = default;
Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {}
operator int() const { return to; }
};
template <typename T = int>
struct Graph {
vector<vector<Edge<T>>> g;
int es;
Graph() = default;
explicit Graph(int n) : g(n), es(0) {}
size_t size() const { return g.size(); }
void add_directed_edge(int from, int to, T cost = 1) { g[from].emplace_back(from, to, cost, es++); }
void add_edge(int from, int to, T cost = 1) {
g[from].emplace_back(from, to, cost, es);
g[to].emplace_back(to, from, cost, es++);
}
void read(int M, int padding = -1, bool weighted = false, bool directed = false, bool reverse = false) {
for (int i = 0; i < M; i++) {
int a, b;
cin >> a >> b;
a += padding;
b += padding;
T c = T(1);
if (weighted) cin >> c;
if (reverse) swap(a, b);
if (directed)
add_directed_edge(a, b, c);
else
add_edge(a, b, c);
}
}
inline vector<Edge<T>> &operator[](const int &k) { return g[k]; }
inline const vector<Edge<T>> &operator[](const int &k) const { return g[k]; }
};
template <typename T = int>
using Edges = vector<Edge<T>>;
class SCC {
private:
vector<int> t;
int v;
vector<int> tmpans;
public:
vector<vector<int>> ans;
Graph<int> g;
Graph<int> g_rev;
SCC(Graph<int> gg, Graph<int> ggrev) {
g = gg;
g_rev = ggrev;
};
// 仕様
// 強連結成分分解の意味とアルゴリズム | 高校数学の美しい物語 https://manabitimes.jp/math/1250
void dfs(int p) {
if (t[p] >= 0) return;
t[p] = 0;
for (auto &&edge : g[p]) {
const int np = edge.to;
if (t[np] >= 0) continue;
dfs(np);
}
t[p] = v++;
}
void dfs2(int p) {
if (t[p] >= 0) return;
tmpans.emplace_back(p);
t[p] = 0;
for (auto &&edge : g_rev[p]) {
const int np = edge.to;
if (t[np] >= 0) continue;
dfs2(np);
}
}
void build() {
// 仕様の1. を行う
t.assign(g.size(), -1);
v = 0;
for (unsigned i = 0; i < g.size(); i++) {
dfs(i);
}
// 仕様の2. を行う
vector<int> t_order(g.size());
for (unsigned i = 0; i < g.size(); i++) {
t_order[t[i]] = i;
}
t.assign(g.size(), -1);
ans.clear();
for (int i = g.size() - 1; i >= 0; i--) {
tmpans.clear();
const int p = t_order[i];
dfs2(p);
if (tmpans.size() > 0) {
ans.emplace_back(tmpans);
}
}
}
};
signed main() {
cin.tie(0);
ios::sync_with_stdio(0);
int n, m;
cin >> n >> m;
Graph g(n);
Graph g_rev(n);
for (int i = 0; i < m; i++) {
int a, b;
cin >> a >> b;
g.add_directed_edge(a, b);
g_rev.add_directed_edge(b, a);
}
SCC scc(g, g_rev);
scc.build();
cout << scc.ans.size() << "\n";
for (auto &&ansi : scc.ans) {
cout << ansi.size() << " ";
for (auto &&i : ansi) {
cout << i << " ";
}
cout << "\n";
}
return 0;
}
verifyした問題
G - SCC 提出 #26087980 - AtCoder Library Practice Contest
読んだ解説
強連結成分分解の意味とアルゴリズム | 高校数学の美しい物語
お気持ち
- 1回目のDFSでトポロジカルソートする。
- 2回目のDFSでトポロジカル順序の末尾から行けるところ(強連結成分)を探す。
- 探したらまた残りの末尾から行けるところ(強連結成分)を探す。
PS
ac-libraryにはSCCがある。 今後SCCはac-libraryのSCCを使う。
https://onlinejudge.u-aizu.ac.jp/status/users/machikane/submissions/1/GRL_2_A/judge/5911208/C++17 https://onlinejudge.u-aizu.ac.jp/status/users/machikane/submissions/1/GRL_2_A/judge/5911209/C++17