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!