Strong Connectivity

# Kosaraju’s Algorithm

This is a template to solve 2SAT.

### 2-SAT

2SAT (Boolean satisfiability problem) is the problem of assigning Boolean values to variables to satisfy a given Boolean formula.

$(x_{1}∨x_{2})∧(x_{3}∨x_{4})∨…$

The original 2-sat logic: You convert the or statements into a series of implications, great video by Algorithms live to rewatch here.

For solving 2SAT, you just follow 2 simple steps:

- Translate the problem in the right variables
- Apply the 2SAT algorithm

The choice of the variables is very important.

`comp[v]`

(comp == component) denotes the index of strongly connected component to which the vertex belongs.

### Finding strongly-connected component

Learned this from CS341. There are 3 simple steps

- Run DFS on G, store the finish time of each vertex
- Run DFS on G^T, starting with vertices with highest finish time
- Each tree in the DFS forest we get from step 2 is a strongly connected component.

Step 2 essentially proceeds like a topological order.