This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub luzhiled1333/comp-library
// verification-helper: PROBLEM https://judge.yosupo.jp/problem/scc #include "src/cpp-template/header/fast-ios.hpp" #include "src/cpp-template/header/int-alias.hpp" #include "src/cpp-template/header/rep.hpp" #include "src/cpp-template/header/size-alias.hpp" #include "src/cpp-template/header/vector-ios.hpp" #include "src/graph/class/edge/edge.hpp" #include "src/graph/class/static-graph.hpp" #include "src/graph/decomposition/strongly-connected-components.hpp" #include <iostream> #include <vector> namespace luz { void main_() { using edge = Edge< i32 >; using graph = StaticGraph< edge >; usize n, m; std::cin >> n >> m; graph g(n); for ([[maybe_unused]] usize _: rep(0, m)) { usize u, v; std::cin >> u >> v; g.add_directed_edge(u, v); } g.initialize(); decomposition::StronglyConnectedComponents scc(g); auto groups = scc.groups(); std::cout << groups.size() << std::endl; for (auto& group: groups) { std::cout << group.size() << " " << group << " " << std::endl; } } } // namespace luz int main() { luz::set_fast_ios(); luz::main_(); }
#line 1 "test/library-checker/scc.test.cpp" // verification-helper: PROBLEM https://judge.yosupo.jp/problem/scc #line 2 "src/cpp-template/header/fast-ios.hpp" #include <iostream> namespace luz { void set_fast_ios() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); } } // namespace luz #line 2 "src/cpp-template/header/int-alias.hpp" #include <cstdint> namespace luz { using i32 = std::int32_t; using i64 = std::int64_t; using i128 = __int128_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using u128 = __uint128_t; } // namespace luz #line 2 "src/cpp-template/header/rep.hpp" #line 2 "src/cpp-template/header/size-alias.hpp" #include <cstddef> namespace luz { using isize = std::ptrdiff_t; using usize = std::size_t; } // namespace luz #line 4 "src/cpp-template/header/rep.hpp" #include <algorithm> namespace luz { struct rep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { ++i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rep(const usize f, const usize l) noexcept : f(std::min(f, l)), l(l) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; struct rrep { struct itr { usize i; constexpr itr(const usize i) noexcept: i(i) {} void operator++() noexcept { --i; } constexpr usize operator*() const noexcept { return i; } constexpr bool operator!=(const itr x) const noexcept { return i != x.i; } }; const itr f, l; constexpr rrep(const usize f, const usize l) noexcept : f(l - 1), l(std::min(f, l) - 1) {} constexpr auto begin() const noexcept { return f; } constexpr auto end() const noexcept { return l; } }; } // namespace luz #line 2 "src/cpp-template/header/vector-ios.hpp" #line 4 "src/cpp-template/header/vector-ios.hpp" #line 6 "src/cpp-template/header/vector-ios.hpp" #include <vector> namespace luz { template < typename T > std::ostream &operator<<(std::ostream &os, const std::vector< T > vs) { for (usize i: rep(0, vs.size())) { os << vs[i] << (i + 1 != vs.size() ? " " : ""); } return os; } template < typename T > std::istream &operator>>(std::istream &is, std::vector< T > &vs) { for (T &v: vs) { is >> v; } return is; } } // namespace luz #line 2 "src/graph/class/edge/edge.hpp" #line 4 "src/graph/class/edge/edge.hpp" #line 6 "src/graph/class/edge/edge.hpp" namespace luz { template < typename T > class Edge { public: using cost_type = T; usize from, to; T cost; usize id; Edge() = default; Edge(usize from_, usize to_, T cost_, usize id_) : from(from_), to(to_), cost(cost_), id(id_) {} }; template < typename T > using Edges = std::vector< Edge< T > >; } // namespace luz #line 2 "src/graph/class/static-graph.hpp" #line 5 "src/graph/class/static-graph.hpp" #line 7 "src/graph/class/static-graph.hpp" #include <cassert> #line 9 "src/graph/class/static-graph.hpp" namespace luz::internal { template < typename Iterator > class OutgoingEdges { Iterator f, l; public: OutgoingEdges(Iterator f, Iterator l): f(f), l(l) {} Iterator begin() const { return f; } Iterator end() const { return l; } usize size() const { return l - f; } auto &operator[](usize k) { assert(k < size()); return begin()[k]; } const auto &operator[](usize k) const { assert(k < size()); return begin()[k]; } }; } // namespace luz::internal namespace luz { template < typename Edge > class StaticGraph { using Edges = std::vector< Edge >; using iterator = typename Edges::iterator; using const_iterator = typename Edges::const_iterator; template < typename Iterator > using Es = internal::OutgoingEdges< Iterator >; protected: bool initialized; usize vertex_count; usize edge_count; Edges edges; std::vector< usize > outdegrees; public: using cost_type = typename Edge::cost_type; StaticGraph() = default; explicit StaticGraph(usize n) : initialized(false), vertex_count(n), edge_count(0), outdegrees(vertex_count) {} usize size() const { return vertex_count; } void initialize() { assert(not initialized); outdegrees.emplace_back(0); for (usize i: rrep(0, size())) { outdegrees[i] += outdegrees[i + 1]; } std::sort(edges.begin(), edges.end(), [](const Edge &e1, const Edge &e2) { return e1.from != e2.from ? e1.from > e2.from : e1.to < e2.to; }); initialized = true; } void add_directed_edge(usize from, usize to, cost_type cost = 1) { assert(not initialized); assert(from < size()); assert(to < size()); edges.emplace_back(from, to, cost, edge_count++); outdegrees[from]++; } void add_undirected_edge(usize u, usize v, cost_type cost = 1) { assert(not initialized); assert(u < size()); assert(v < size()); assert(u != v); edges.emplace_back(u, v, cost, edge_count); outdegrees[u]++; edges.emplace_back(v, u, cost, edge_count++); outdegrees[v]++; } Es< iterator > operator[](const usize &v) { assert(initialized); return Es< iterator >(edges.begin() + outdegrees[v + 1], edges.begin() + outdegrees[v]); } const Es< const_iterator > operator[](const usize &v) const { assert(initialized); return Es< const_iterator >(edges.cbegin() + outdegrees[v + 1], edges.cbegin() + outdegrees[v]); } }; } // namespace luz #line 2 "src/graph/decomposition/strongly-connected-components.hpp" #line 2 "src/cpp-template/header/change-min.hpp" namespace luz { template < typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b and (a = b, true); } } // namespace luz #line 6 "src/graph/decomposition/strongly-connected-components.hpp" #line 8 "src/graph/decomposition/strongly-connected-components.hpp" namespace luz::decomposition { template < class G > class StronglyConnectedComponents { using graph = G; using cost_type = typename graph::cost_type; graph g; usize g_size; std::vector< usize > low, ord, visited, group_id; usize ord_cnt, group_cnt; void dfs(usize v) { low[v] = ord[v] = ord_cnt++; visited.emplace_back(v); for (auto& e: g[v]) { if (ord[e.to] == g_size) { dfs(e.to); chmin(low[v], low[e.to]); } else { chmin(low[v], ord[e.to]); } } if (low[v] == ord[v]) { while (true) { usize u = visited.back(); visited.pop_back(); ord[u] = g_size + 1; group_id[u] = group_cnt; if (u == v) break; } group_cnt++; } } public: explicit StronglyConnectedComponents(const graph& g_) : g(g_), g_size(g.size()), low(g_size), ord(g_size, g_size), group_id(g_size), ord_cnt(0), group_cnt(0) { visited.reserve(g_size); for (usize v: rep(0, g_size)) { if (ord[v] == g_size) { dfs(v); } } for (auto& id: group_id) { id = group_cnt - id - 1; } } std::vector< std::vector< usize > > groups() const { std::vector< usize > counts(group_cnt); for (usize i: rep(0, g_size)) { counts[group_id[i]]++; } std::vector< std::vector< usize > > groups(group_cnt); for (usize i: rep(0, group_cnt)) { groups[i].reserve(counts[i]); } for (usize i: rep(0, g_size)) { groups[group_id[i]].emplace_back(i); } return groups; } std::vector< usize > group_ids() const { return group_id; } }; } // namespace luz::decomposition #line 11 "test/library-checker/scc.test.cpp" #line 14 "test/library-checker/scc.test.cpp" namespace luz { void main_() { using edge = Edge< i32 >; using graph = StaticGraph< edge >; usize n, m; std::cin >> n >> m; graph g(n); for ([[maybe_unused]] usize _: rep(0, m)) { usize u, v; std::cin >> u >> v; g.add_directed_edge(u, v); } g.initialize(); decomposition::StronglyConnectedComponents scc(g); auto groups = scc.groups(); std::cout << groups.size() << std::endl; for (auto& group: groups) { std::cout << group.size() << " " << group << " " << std::endl; } } } // namespace luz int main() { luz::set_fast_ios(); luz::main_(); }