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)
Tarjan's Algorithm
Resources | ||||
---|---|---|---|---|
CPC | ||||
CP2 | ||||
Wikipedia |
Solution (Tarjan's)
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!