This week's episode will cover how to use lowlinking to extract the strongly connected components from directed graphs.
00:58 Definition of strongly connected components
02:58 Warshall's transitive closure algorithm O(V^3)
05:18 Refresher on edge types during DFS
06:35 Properties of SCC in DFS
10:15 Detecting and extracting SCC during DFS
15:40 Extracting SCC example by hand
22:56 Building meta-graph, properties
28:23 Coding Tarjan's SCC algorithm
44:47 Equivalences problem
47:46 Algorithm overview
49:53 Lower bound on number of edges to add
55:23 Coding solution to Equivalences
Thank you to Mikhail Goncharov for the time links!
