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 $ID$ (starting from $1$).

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!