PrevNext
Rare
 0/11

Strongly Connected Components

Authors: Benjamin Qi, Dong Liu, Neo Wang

Subsets of nodes in directed graphs where each node in a subset can reach each other node in the subset.

SCCs

Focus Problem – try your best to solve this problem before continuing!

View Internal Solution

The definition of a kingdom in this problem is equivalent to the definition of a strongly connected component. We can compute these components using either Kosaraju's or Tarjan's algorithms, both of which are described below.

Kosaraju's Algorithm

Solution (Kosaraju's)

C++

#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

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];

Tarjan's Algorithm

Solution (Tarjan's)

C++

#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

Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsDP, SCC
POIEasy
Show TagsDP, SCC
CFNormal
Show TagsDP, SCC
Old GoldNormal
Show TagsSCC
CFNormal
Show TagsSCC
CFHard
Show TagsSCC
POIHard
Show TagsSCC
KattisHard
Show TagsSCC
CSESVery Hard
Show TagsSCC

2-SAT

Focus Problem – try your best to solve this problem before continuing!

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

implementation

Tutorial

Resources
CF
cp-algo
Algorithms Live!

This section is not complete.

Any help would be appreciated! Just submit a Pull Request on Github.

mention KACTL - at most one

Module Progress:

Join the USACO Forum!

Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!

PrevNext