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

$0 \leq n \leq 10^8$

Complexity

$O(n)$

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

$O(1)$ amortized

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

AC code of https://atcoder.jp/contests/practice2/tasks/practice2_g

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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;
}
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX