PrevNext
Rare
 0/10

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 – read through 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)

Tarjan's Algorithm

Solution (Tarjan's)

Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsDP, SCC
POIEasy
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 – read through 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

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