Strongly Connected Components

TL;DR In this blog post, we will explore examples illustrating why alternate variations of Kosaraju-Sharir’s algorithm for computing strongly connected components fail. Prerequisites I assume that reader is already familiar with the below topics: Strongly connected component problem Rough idea of Kosaraju Sharir Algorithm1. Finally, a handy reference to clrs book as we will be using the conceptual framework from this book. Terminology Discovery time of a vertex: When a vertex is first discovered. Denoted as v.discovery finish time of a vertex: When the vertex is fully explored and recursive dfs function for the vertex returns. Denoted as v.finish Conventions used: An edge being explored is in bold red color and an edge in blue color is part of dfs tree. Time is monotonically increasing and it starts from 1. discovery_time/finish_time times appear below the node. Nodes are that fully processed are in blue color and currently being explored are in red color. Consider an example of running dfs from a vertex a ...