Strong Connectivity is a thing we use only in directed graphs. Definition of Directed Graphs HERE

**Def**

Nodes **a **and** b** in a graph are mutually reachable if there is both a path from **a **to **b **and also a path from **b** to **a**. If all the nodes in the graph are mutually reachable in directed graph it is strongly connected .

**Lemma.** Let s be any node in graph ** G**, Graph **G** is strongly connected if and only if (iff) s is reachable from every other node and every node is reachable from s.

**How to determine strong connectivity in Graph?**

**Time Complexity: O(m+n)**

- Pick any node s
- Run BFS from s in G. (BFS: Breadth First Search . Definition HERE)
- Check that s reaches all other nodes or not.
- Now reverse the Edges in the Graph ( Head becomes Tail and Tail becomes Head)
- Run BFS again on the reversed Graph.
- if s reaches all the nodes in graph G and graph G-reversed.
- then Strongly connected graph is G.

**Strong Component**

A strong component is maximal subset of mutually reachable nodes. For example there is a large graph having nodes from **a-f** and the graph is not strongly connected. In the graph there may be three nodes, suppose a-c which are mutually reachable from each other. So **a-c **is strong component in graph **a-f.**

#### **How to find Strong Components in Graph?**

**Time Complexity: O(m+n)**

- Pick any node a
- Run DFS from s in G. (DFS: Depth First Search . Definition HERE)
- Now reverse the Edges in the Graph ( Head becomes Tail and Tail becomes Head)
- Run DFS again on the reversed Graph. But start from the node which was last in Previous DFS.
- Output the forest formed by both the DFS iterations. If both contain same nodes they are strong component.

#### READ MORE

**Algorithms **related posts visit **HERE**

**Data Structures **related posts visit **HERE**

**Databases** related posts Visit **HERE**

**Python-related** posts Visit **HERE**

**C++** related posts Visit **HERE**

**Data Science** related posts visit **HERE**