test/library-checker/Graph/SCC.test.cpp
Depends on
Code
#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#include <bits/stdc++.h>
#include "library/graph/Graph.hpp"
#include "library/graph/SCC.hpp"
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
Graph g(n, m, true, 0);
SCC scc(g);
int k = scc.DAG.n;
std::cout << k << "\n";
for (const auto &ve : scc.component) {
std::cout << ve.size();
for (int p : ve)
std::cout << " " << p;
std::cout << "\n";
}
}
#line 1 "test/library-checker/Graph/SCC.test.cpp"
#define PROBLEM "https://judge.yosupo.jp/problem/scc"
#include <bits/stdc++.h>
#line 2 "library/graph/Graph.hpp"
#line 6 "library/graph/Graph.hpp"
struct Edge {
int from, to;
Edge() = default;
Edge(int from, int to) : from(from), to(to) {}
operator int() const { return to; }
};
struct Graph {
int n;
using edge_type = Edge;
std::vector<edge_type> edges;
protected:
std::vector<int> in_deg;
bool prepared;
class OutgoingEdges {
Graph *g;
int l, r;
public:
OutgoingEdges(Graph *g, int l, int r) : g(g), l(l), r(r) {}
edge_type *begin() { return &(g->edges[l]); }
edge_type *end() { return &(g->edges[r]); }
edge_type &operator[](int i) { return g->edges[l + i]; }
int size() const { return r - l; }
};
class ConstOutgoingEdges {
const Graph *g;
int l, r;
public:
ConstOutgoingEdges(const Graph *g, int l, int r) : g(g), l(l), r(r) {}
const edge_type *begin() const { return &(g->edges[l]); }
const edge_type *end() const { return &(g->edges[r]); }
const edge_type &operator[](int i) const { return g->edges[l + i]; }
int size() const { return r - l; }
};
public:
OutgoingEdges operator[](int v) {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
const ConstOutgoingEdges operator[](int v) const {
assert(prepared);
return {this, in_deg[v], in_deg[v + 1]};
}
bool is_prepared() const { return prepared; }
Graph() : n(0), in_deg(1, 0), prepared(false) {}
Graph(int n) : n(n), in_deg(n + 1, 0), prepared(false) {}
Graph(int n, int m, bool directed = false, int indexed = 1)
: n(n), in_deg(n + 1, 0), prepared(false) {
scan(m, directed, indexed);
}
void resize(int n) { n = n; }
void add_arc(int from, int to) {
assert(!prepared);
assert(0 <= from and from < n and 0 <= to and to < n);
edges.emplace_back(from, to);
in_deg[from + 1]++;
}
void add_edge(int u, int v) {
add_arc(u, v);
add_arc(v, u);
}
void add_arc(const edge_type &e) { add_arc(e.from, e.to); }
void add_edge(const edge_type &e) { add_edge(e.from, e.to); }
void scan(int m, bool directed = false, int indexed = 1) {
edges.reserve(directed ? m : 2 * m);
while (m--) {
int u, v;
std::cin >> u >> v;
u -= indexed;
v -= indexed;
if (directed)
add_arc(u, v);
else
add_edge(u, v);
}
build();
}
void build() {
assert(!prepared);
prepared = true;
for (int v = 0; v < n; v++)
in_deg[v + 1] += in_deg[v];
std::vector<edge_type> new_edges(in_deg.back());
auto counter = in_deg;
for (auto &&e : edges)
new_edges[counter[e.from]++] = e;
edges = new_edges;
}
void graph_debug() const {
#ifndef __LOCAL
return;
#endif
assert(prepared);
for (int from = 0; from < n; from++) {
std::cerr << from << ";";
for (int i = in_deg[from]; i < in_deg[from + 1]; i++)
std::cerr << edges[i].to << " ";
std::cerr << "\n";
}
}
};
#line 2 "library/graph/ReverseGraph.hpp"
template <typename GRAPH> GRAPH reverse_graph(const GRAPH &g) {
GRAPH r(g.n);
for (auto e : g.edges) {
std::swap(e.from, e.to);
r.add_arc(e);
}
r.build();
return r;
}
#line 4 "library/graph/SCC.hpp"
#define REP_(i, n) for (int i = 0; i < (n); i++)
template <typename DirectedGraph> class SCC {
int n;
DirectedGraph G, R;
std::vector<int> visit, belong;
std::vector<uint8_t> used;
void dfs(int v) {
used[v] = true;
for (int to : G[v])
if (!used[to])
dfs(to);
visit.push_back(v);
}
void rdfs(int v, int k) {
used[v] = true;
belong[v] = k;
for (int to : R[v])
if (!used[to])
rdfs(to, k);
}
public:
Graph DAG;
std::vector<std::vector<int>> component;
SCC(const DirectedGraph &G) : n(G.n), G(G), belong(n), used(n, false) {
assert(G.is_prepared());
visit.reserve(n);
R = reverse_graph(G);
REP_(v, n) if (!used[v]) dfs(v);
std::ranges::fill(used, false);
std::ranges::reverse(visit);
int k = 0;
for (const int &v : visit)
if (!used[v])
rdfs(v, k++);
std::vector<std::vector<int>> edges(k);
component.resize(k);
REP_(v, n) {
component[belong[v]].push_back(v);
for (int to : G[v])
if (belong[v] != belong[to])
edges[belong[v]].push_back(belong[to]);
}
DAG = Graph(k);
REP_(from, k) {
std::ranges::sort(edges[from]);
REP_(i, edges[from].size())
if (!i || edges[from][i] != edges[from][i - 1])
DAG.add_arc(from, edges[from][i]);
}
}
int operator[](int k) { return belong[k]; }
};
#undef REP_
#line 6 "test/library-checker/Graph/SCC.test.cpp"
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
int n, m;
std::cin >> n >> m;
Graph g(n, m, true, 0);
SCC scc(g);
int k = scc.DAG.n;
std::cout << k << "\n";
for (const auto &ve : scc.component) {
std::cout << ve.size();
for (int p : ve)
std::cout << " " << p;
std::cout << "\n";
}
}
Back to top page
build/pch/stdc++.hpp