This documentation is automatically generated by online-judge-tools/verification-helper
#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#include <iostream>
#include "../algorithm/Graph/Others/strongly_connected_components.hpp"
#include "../algorithm/Graph/Others/topological_sort.hpp"
int main() {
int n;
int m;
std::cin >> n >> m;
algorithm::SCC scc(n);
for(int i = 0; i < m; ++i) {
int a, b;
std::cin >> a >> b;
scc.add_edge(a, b);
}
auto &&[num, ids] = scc.decompose();
auto &&sccs = scc.scc(num, ids);
auto &&dag = scc.directed_acyclic_graph(num, ids);
algorithm::TopologicalSort ts(num);
for(int u = 0; u < num; ++u) {
for(auto v : dag[u]) ts.add_edge(u, v);
}
auto &&v = ts.topological_sort();
std::cout << num << "\n";
for(auto id : v) {
std::cout << sccs[id].size() << " ";
for(auto v : sccs[id]) std::cout << v << " ";
std::cout << "\n";
}
}
#line 1 "verify/yosupo-scc-strongly_connected_components.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#include <iostream>
#line 1 "algorithm/Graph/Others/strongly_connected_components.hpp"
/**
* @brief Strongly Connected Components(強連結成分分解)
* @docs docs/Graph/Others/strongly_connected_components.md
*/
#include <algorithm>
#include <cassert>
#include <stack>
#include <utility>
#include <vector>
namespace algorithm {
// Strongly Connected Components(強連結成分分解).
class SCC {
int m_vn; // m_vn:=(ノード数).
std::vector<std::vector<int> > m_g; // m_g[v][]:=(ノードvの隣接リスト).
public:
SCC() : SCC(0) {}
explicit SCC(int vn) : m_vn(vn), m_g(vn) {}
// ノード数を返す.
int order() const { return m_vn; }
// 有向辺を張る.
void add_edge(int from, int to) {
assert(0 <= from and from < order());
assert(0 <= to and to < order());
m_g[from].push_back(to);
}
// 有向グラフを強連結成分分解する.return pair of (# of SCCs, SCC id of each nodes). O(|V|+|E|).
std::pair<int, std::vector<int> > decompose() const {
int num_sccs = 0; // num_sccs:=(SCCの数).
std::vector<int> ids(order()); // ids[v]:=(ノードvが属するSCCのID).
// ord[v]:=(DFS木におけるノードvの行きがけ順序).
// low[v]:=(DFS木において,ノードvから葉方向への辺を0回以上,後退辺を高々1回用いて到達できるノードwに対するord[w]の最小値).
std::vector<int> ord(order(), -1), low(order());
int now = 0;
std::stack<int> visited;
auto dfs = [&](auto self, int u) -> void {
ord[u] = low[u] = now++;
visited.push(u);
for(int to : m_g[u]) {
if(ord[to] == -1) {
self(self, to);
low[u] = std::min(low[u], low[to]);
} else {
low[u] = std::min(low[u], ord[to]);
}
}
if(low[u] == ord[u]) {
while(true) {
int v = visited.top();
visited.pop();
ord[v] = order(); // inf.
ids[v] = num_sccs;
if(v == u) break;
}
num_sccs++;
}
};
for(int v = 0; v < order(); ++v) {
if(ord[v] == -1) dfs(dfs, v);
}
return {num_sccs, ids};
}
// 強連結成分ごとに各ノードをグループ分けする.
std::vector<std::vector<int> > scc() const { return scc(decompose()); }
std::vector<std::vector<int> > scc(const std::pair<int, std::vector<int> > &p) const { return scc(p.first, p.second); }
std::vector<std::vector<int> > scc(int num, const std::vector<int> &ids) const {
assert((int)ids.size() == order());
std::vector<std::vector<int> > sccs(num);
for(int v = 0; v < order(); ++v) {
assert(0 <= ids[v] and ids[v] < num);
sccs[ids[v]].push_back(v);
}
return sccs;
}
// 強連結成分から構成されるDAGを取得する.
std::vector<std::vector<int> > directed_acyclic_graph(const std::pair<int, std::vector<int> > &p) const { return directed_acyclic_graph(p.first, p.second); }
std::vector<std::vector<int> > directed_acyclic_graph(int num, const std::vector<int> &ids) const {
assert((int)ids.size() == order());
std::vector<std::vector<int> > dag(num);
for(int u = 0; u < order(); ++u) {
assert(0 <= ids[u] and ids[u] < num);
for(int v : m_g[u]) {
assert(0 <= ids[v] and ids[v] < num);
if(ids[v] == ids[u]) continue;
dag[ids[u]].push_back(ids[v]);
}
}
for(std::vector<int> &edge : dag) {
std::sort(edge.begin(), edge.end());
edge.erase(std::unique(edge.begin(), edge.end()), edge.end());
}
return dag;
}
};
} // namespace algorithm
#line 1 "algorithm/Graph/Others/topological_sort.hpp"
/**
* @brief Topological Sort(トポロジカルソート)
* @docs docs/Graph/Others/topological_sort.md
*/
#line 10 "algorithm/Graph/Others/topological_sort.hpp"
#include <queue>
#line 12 "algorithm/Graph/Others/topological_sort.hpp"
namespace algorithm {
class TopologicalSort {
int m_vn; // m_vn:=(ノード数).
std::vector<std::vector<int> > m_g; // m_g[v]:=(ノードvの隣接リスト).
public:
TopologicalSort() : TopologicalSort(0) {}
explicit TopologicalSort(size_t vn) : m_vn(vn), m_g(vn) {}
// ノード数を返す.
int order() const { return m_vn; }
// 有向辺を張る.
void add_edge(int from, int to) {
assert(0 <= from and from < order());
assert(0 <= to and to < order());
m_g[from].push_back(to);
}
// 有向非巡回グラフに対する任意のトポロジカルソートの解を求める.O(|V|+|E|).
std::vector<int> topological_sort() const {
std::vector<int> res;
res.reserve(order());
std::vector<int> deg(order(), 0); // deg[v]:=(ノードvの入次数).
for(const std::vector<int> &edges : m_g) {
for(int to : edges) deg[to]++;
}
std::queue<int> que;
for(int i = 0; i < order(); ++i) {
if(deg[i] == 0) que.push(i);
}
while(!que.empty()) {
int u = que.front();
que.pop();
res.push_back(u);
for(int v : m_g[u]) {
if(--deg[v] == 0) que.push(v);
}
}
if((int)res.size() != order()) return std::vector<int>(); // 閉路がある場合.
return res;
}
// 考え得るトポロジカルソートの解を数え上げる.ノード数の実用上限目安は20程度.O(N*(2^N)).
template <typename Type = long long>
Type count_up() const {
assert(order() <= 30);
const int n = order();
std::vector<int> b(n, 0); // b[v]:=(ノードvの隣接リストにある行き先ノードの集合).
for(int v = 0; v < n; ++v) {
for(int to : m_g[v]) b[v] |= 1 << to;
}
std::vector<Type> dp(1 << n, 0); // dp[S]:=(ノード集合Sにおける解の通り数).
dp[0] = 1;
for(int bit = 0; bit < 1 << n; ++bit) {
for(int i = 0; i < n; ++i) {
if(!(bit >> i & 1) and !(bit & b[i])) dp[bit | 1 << i] += dp[bit];
}
}
return dp[(1 << n) - 1];
}
};
} // namespace algorithm
#line 7 "verify/yosupo-scc-strongly_connected_components.test.cpp"
int main() {
int n;
int m;
std::cin >> n >> m;
algorithm::SCC scc(n);
for(int i = 0; i < m; ++i) {
int a, b;
std::cin >> a >> b;
scc.add_edge(a, b);
}
auto &&[num, ids] = scc.decompose();
auto &&sccs = scc.scc(num, ids);
auto &&dag = scc.directed_acyclic_graph(num, ids);
algorithm::TopologicalSort ts(num);
for(int u = 0; u < num; ++u) {
for(auto v : dag[u]) ts.add_edge(u, v);
}
auto &&v = ts.topological_sort();
std::cout << num << "\n";
for(auto id : v) {
std::cout << sccs[id].size() << " ";
for(auto v : sccs[id]) std::cout << v << " ";
std::cout << "\n";
}
}