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 SolutionThe 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

Resources | ||||
---|---|---|---|---|

CPH | ||||

Wikipedia |

### Solution (Kosaraju's)

C++

#include <bits/stdc++.h>using namespace std;using vi = vector<int>;#define pb push_backconst int mx = 1e5 + 1;// adj_t is the transpose of adjvi 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 neighborstatic List<Integer>[] adj = new ArrayList[N + 1];// adjT is the transpose of adjstatic List<Integer>[] adjT = new ArrayList[N + 1];

### Tarjan's Algorithm

Resources | ||||
---|---|---|---|---|

CPC | ||||

CP2 | ||||

Wikipedia |

### 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

Status | Source | Problem Name | Difficulty | Tags | |
---|---|---|---|---|---|

CSES | Easy | ## Show TagsDP, SCC | |||

POI | Easy | ## Show TagsDP, SCC | |||

CF | Normal | ## Show TagsDP, SCC | |||

Old Gold | Normal | ## Show TagsSCC | |||

CF | Normal | ## Show TagsSCC | |||

CF | Hard | ## Show TagsSCC | |||

POI | Hard | ## Show TagsSCC | |||

Kattis | Hard | ## Show TagsSCC | |||

CSES | Very 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

### 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!