# Notes - DAA HT23, Strongly connected components

### Flashcards

What a strongly connected component of a graph $G$?

A maximal set of vertices $C \subseteq V$ such that for every pair of vertices $u \leadsto v$ and $v \leadsto u$.

Can you give the very high-level pseudocode for the strongly connected components algorithm on a graph $G$?

```
STRONGLY-CONNECTED-COMPONENTS(G):
call DFS(G) to compute the finish times u.f for each vertex u
create G^T
call DFS(G^T), but in the main loop of DFS consider the vertices in order of decreasing u.f
output the vertices of each tree in the depth-first forest formed in the second DFS as seperate strongly connected components
```

When running the strongly connected components algorithm on a graph $G$, in what order do you consider the vertices after the initial depth-first search?

In order of decreasing finishing time, i.e. topological order.

When constructing a topological sort of a DAG, what order do you consider vertices in?

Reverse finishing time.