#define PROBLEM "https://judge.yosupo.jp/problem/scc" #include <iostream> #include <vector> #include "Mylib/Graph/GraphUtils/strongly_connected_components.cpp" #include "Mylib/Graph/Template/graph.cpp" #include "Mylib/IO/join.cpp" namespace hl = haar_lib; int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); int N, M; std::cin >> N >> M; hl::graph<int> g(N); g.read<0, true, false>(M); auto [scc, K] = hl::strongly_connected_components(g); std::vector<std::vector<int>> ans(K); for (int i = 0; i < N; ++i) ans[scc[i]].push_back(i); std::cout << K << "\n"; for (auto &t : ans) { std::cout << t.size() << " " << hl::join(t.begin(), t.end()) << "\n"; } return 0; }
#line 1 "test/yosupo-judge/scc/main.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/scc" #include <iostream> #include <vector> #line 2 "Mylib/Graph/GraphUtils/strongly_connected_components.cpp" #include <algorithm> #line 4 "Mylib/Graph/Template/graph.cpp" namespace haar_lib { template <typename T> struct edge { int from, to; T cost; int index = -1; edge() {} edge(int from, int to, T cost) : from(from), to(to), cost(cost) {} edge(int from, int to, T cost, int index) : from(from), to(to), cost(cost), index(index) {} }; template <typename T> struct graph { using weight_type = T; using edge_type = edge<T>; std::vector<std::vector<edge<T>>> data; auto& operator[](size_t i) { return data[i]; } const auto& operator[](size_t i) const { return data[i]; } auto begin() const { return data.begin(); } auto end() const { return data.end(); } graph() {} graph(int N) : data(N) {} bool empty() const { return data.empty(); } int size() const { return data.size(); } void add_edge(int i, int j, T w, int index = -1) { data[i].emplace_back(i, j, w, index); } void add_undirected(int i, int j, T w, int index = -1) { add_edge(i, j, w, index); add_edge(j, i, w, index); } template <size_t I, bool DIRECTED = true, bool WEIGHTED = true> void read(int M) { for (int i = 0; i < M; ++i) { int u, v; std::cin >> u >> v; u -= I; v -= I; T w = 1; if (WEIGHTED) std::cin >> w; if (DIRECTED) add_edge(u, v, w, i); else add_undirected(u, v, w, i); } } }; template <typename T> using tree = graph<T>; } // namespace haar_lib #line 5 "Mylib/Graph/GraphUtils/strongly_connected_components.cpp" namespace haar_lib { template <typename T> auto strongly_connected_components(const graph<T> &g) { const int n = g.size(); std::vector<int> ret(n), low(n, -1), ord(n, -1), S; std::vector<bool> check(n); S.reserve(n); int t = 0; int k = 0; auto dfs = [&](auto &dfs, int cur) -> void { low[cur] = ord[cur] = t++; S.push_back(cur); check[cur] = true; for (auto &e : g[cur]) { if (ord[e.to] == -1) { dfs(dfs, e.to); low[cur] = std::min(low[cur], low[e.to]); } else if (check[e.to]) { low[cur] = std::min(low[cur], low[e.to]); } } if (low[cur] == ord[cur]) { while (true) { int u = S.back(); S.pop_back(); check[u] = false; ret[u] = k; if (cur == u) break; } ++k; } }; for (int i = 0; i < n; ++i) { if (ord[i] == -1) { t = 0; dfs(dfs, i); } } for (auto &x : ret) x = k - 1 - x; return std::make_pair(ret, k); } } // namespace haar_lib #line 3 "Mylib/IO/join.cpp" #include <sstream> #include <string> namespace haar_lib { template <typename Iter> std::string join(Iter first, Iter last, std::string delim = " ") { std::stringstream s; for (auto it = first; it != last; ++it) { if (it != first) s << delim; s << *it; } return s.str(); } } // namespace haar_lib #line 8 "test/yosupo-judge/scc/main.test.cpp" namespace hl = haar_lib; int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); int N, M; std::cin >> N >> M; hl::graph<int> g(N); g.read<0, true, false>(M); auto [scc, K] = hl::strongly_connected_components(g); std::vector<std::vector<int>> ans(K); for (int i = 0; i < N; ++i) ans[scc[i]].push_back(i); std::cout << K << "\n"; for (auto &t : ans) { std::cout << t.size() << " " << hl::join(t.begin(), t.end()) << "\n"; } return 0; }