Strongly Connected Components

C++

Copy
#include <bits/stdc++.h>  // see /general/running-code-locally
using namespace std;

using vi = vector<int>;
#define pb push_back

const int mx = 1e5 + 1;

// adj_t is the transpose of adj
vi adj[mx], adj_t[mx], S;

C++

Copy
#include <bits/stdc++.h>
using namespace std;
/**
 * Description: Tarjan's, DFS once to generate
 * strongly connected components in topological order. $a,b$
 * in same component if both $a\to b$ and $b\to a$ exist.
 * Uses less memory than Kosaraju b/c doesn't store reverse edges.
 * Time: O(N+M)
 * Source: KACTL
 * https://github.com/kth-competitive-programming/kactl/blob/master/content/graph/SCC.h