> For the complete documentation index, see [llms.txt](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://maksimdan.gitbook.io/ecs122a-algorithm-design-lecture-notes/basic_graph_algorithms/strongly_connected_components.md).

# Strongly Connected Components

* Two nodes are considered to be mutually connected if you can go from node a to node b and from node b to node a.
* A graph is said to be strongly connected if every node is mutually connected. That is, every node can reach every other node and vise versa.

## English Algorithm

1. Start from any node S.
2. Preform DFS starting from node S. Add elements by their earliest finish time into a stack. An node is considered to be *finished* when it can no longer explore any children.
3. Step 1, until all nodes of the graph are explored.
4. Reverse all the edges in graph
5. Start from any node S in the reversed graph.
6. Perform DFS starting from elements on top of the stack, popping off you go. Explore node S, and this will return the elements within the strongly connected component.

\*\* Ensure that during this process, nodes are visited only once.

**Time Complexity:** $$O(V+E)$$ - 2 linear time dfs calls **Space Complexity:** $$O(V)$$ - stack and vector returns proportional to the number of original vertices in the graph.

### Example

The following graph has 4 strongly connected components.

![](https://4248470099-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphnGN5n2jKpXzYL%2F-LoJHqLx4tZP9WYw_RQZ%2F-LoJI-QDC4hFoMGVHXCF%2FSCC_ex.PNG?generation=1568003598411755\&alt=media)

```
K
A B C
D E F
H I J G
```

## Why this Works

Consider the simplified version of this graph

![](https://4248470099-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-LoJHphnGN5n2jKpXzYL%2F-LoJHqLx4tZP9WYw_RQZ%2F-LoJI-QFcO0GSCXpPNDB%2FSCC_s1.PNG?generation=1568003598215488\&alt=media)

Where every strongly connected component is represented as a single node in this graph. The remaining edges that connect the these components together produce the remainder of the graph.

We know a few things about this graph. First, it is guaranteed to be a DAG. If it was otherwise cyclic, then the cycle would mean there would be another simplification the above graph that would combine two strongly connected components.

Secondly, the order of earliest finish would mean that there is at least one node in `ABC` that remains unexplored because the DFS algorithm would continue to explore `DEF`.

So if we transpose this graph, then we are ensuring that the nodes finished first get explored last. So now even if `DEF` has the chance to explore both `ABC` and `HIGJ` the algorithm ensure that both of these components were already explored and so `DEF` remains on its own.