SCC
It calculates the strongly connected components of directed graphs.
Constructor
scc_graph graph(int n)
It creates a directed graph with $n$ vertices and $0$ edges.
Constraints
Complexity
add_edge
void graph.add_edge(int from, int to)
It adds a directed edge from the vertex from to the vertex to.
Constraints
- $0 \leq \mathrm{from} \lt n$
- $0 \leq \mathrm{to} \lt n$
Complexity
scc
vector<vector<int>> graph.scc()
It returns the list of the "list of the vertices" that satisfies the following.
- Each vertex is in exactly one "list of the vertices".
- Each "list of the vertices" corresponds to the vertex set of a strongly connected component. The order of the vertices in the list is undefined.
- The list of "list of the vertices" are sorted in topological order, i.e., for two vertices $u, v$ in different strongly connected components, if there is a directed path from $u$ to $v$, the list contains $u$ appears earlier than the list contains $v$.
Complexity
- $O(n + m)$, where $m$ is the number of added edges.
Examples
#include <atcoder/scc>
#include <cstdio>
using namespace std;
using namespace atcoder;
int main() {
int n, m;
scanf("%d %d", &n, &m);
scc_graph g(n);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d %d", &u, &v);
g.add_edge(u, v);
}
auto scc = g.scc();
printf("%d\n", int(scc.size()));
for (auto v : scc) {
printf("%d", int(v.size()));
for (int x : v) {
printf(" %d", x);
}
printf("\n");
}
return 0;
}