Strongly Connected Components

C++

Copy
#include <bits/stdc++.h>
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;

Java

Copy
import java.io.*;
import java.util.*;

public class Main {
	static final int N = 100001;
	static boolean[] vis = new boolean[N + 1];
	// Adjacency list of neighbor
	static List<Integer>[] adj = new ArrayList[N + 1];
	// adjT is the transpose of adj
	static List<Integer>[] adjT = new ArrayList[N + 1];

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