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