A directed graph is strongly connected if there is a directed path from any vertex to every other vertex. Strong connectivity applies only to directed graphs because in an undirected graph, every vertex can reach every other vertex via any path. This relation between nodes is reflexive, symmetric, and transitive, so it is an equivalence relation. If the graph is not connected the graph can be broken down into Connected Components.
A directed graph cane be decomposed into its strongly connected components using depth-first search. Generally speaking, the connected components of the graph correspond to different classes of objects. Tarjan’s algorithm is a procedure for finding strongly connected components of a directed graph. A strongly connected component is a maximum set of vertices, in which exists at least one oriented path between every two vertices.
Given a directed graph G = (V, E), a strongly connected component (SCC) of G is a maximal set of vertices C subset of V, such that for all u, v in C, both u ⇒ v and v⇒u i.e. both u and v are reachable from each other. In other words, two vertices of directed graph are in the same component if and only if they are reachable from each other. Below directed graph has 4 strongly connected components: C1, C2, C3 and C4.
The graph of below figure has five SSC. Shrink each strongly connected component down to a single meta-node, and draw an edge from one meta-node to another if there is an edge (in the same direction) between their respective components (Figure b). The resulting meta-graph must be a directed acyclic graph. The reason is simple : a cycle containing several strongly connected components would merge them all into a single strongly connected component.
Thus the connectivity structure of a directed graph is two-tiered. At the top level we have a DAG, which must always have a source and a sink. We can look inside one of the nodes of this DAG for more details and examine the full -fledged strongly connected component within.
Therefore, if we can find a node which lies somewhere in a sink strongly connected component (a strongly connected component which is a sink in the meta graph), then DFS on this node will retrieve exactly that component. Above figure (b) has two sink strongly connected components.