PrevNext
Rare
 0/9

Strongly Connected Components

Authors: Benjamin Qi, Dong Liu

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

SCCs

Tutorial

Resources
CPH
CPC
CP2
Benq

concise implementation of Kosaraju's Algorithm

Benq

concise implementation of Tarjan's Algorithm

Focus Problem – read through this problem before continuing!

Solution - Planets and Kingdoms

Just run Kosaraju's or Tarjan's SCC algorithm on the graph.

Then assign each component an IDID (starting from 11).

Using Kosaraju's SCC

Using Tarjan's SCC

Problems

StatusSourceProblem NameDifficultyTags
CSESEasy
Show TagsDP, SCC
POIEasy
Show TagsSCC, dp
Old GoldNormal
CFNormal
POIHard
KattisHard
CSESHard

2-SAT

StatusSourceProblem NameDifficultyTags
CSESNormal

(impl)

Tutorial

Resources
CF

(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