Rare
0/9
Strongly Connected Components
Authors: Benjamin Qi, Dong Liu
Prerequisites
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 (starting from ).
Using Kosaraju's SCC
Using Tarjan's SCC
Problems
Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|
CSES | Easy | Show TagsDP, SCC | |||||||
POI | Easy | Show TagsSCC, dp | |||||||
Old Gold | Normal | ||||||||
CF | Normal | ||||||||
POI | Hard | ||||||||
Kattis | Hard | ||||||||
CSES | Hard | ||||||||
2-SAT
Status | Source | Problem Name | Difficulty | Tags | |||||
---|---|---|---|---|---|---|---|---|---|
CSES | Normal | ||||||||
(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!