# Tarjan

Tarjan's strongly connected components algorithm is an algorithm in graph theory for finding the **strongly connected components (SCCs)** of a directed graph. It runs in linear time, matching the time bound for alternative methods including Kosaraju's algorithm and the path-based strong component algorithm. The algorithm is named for its inventor, Robert Tarjan.

![](https://851655761-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7JACxIEuMBezDCzfss%2Fsync%2F0c260832ea4aa07cd7fdc50bff95c439d55ab260.png?generation=1632902330081628\&alt=media)

![](https://851655761-files.gitbook.io/~/files/v0/b/gitbook-legacy-files/o/assets%2F-M7JACxIEuMBezDCzfss%2Fsync%2F615dea9b8664f78a775d25ec13b823b5b184e499.png?generation=1632902330935169\&alt=media)

## References

* [https://en.wikipedia.org/wiki/Tarjan%27s\_strongly\_connected\_components\_algorithm](https://en.wikipedia.org/wiki/Tarjan's_strongly_connected_components_algorithm)
* \[Tarjans Strongly Connected Components algorithm | Graph Theory

  ]\(<https://youtu.be/TyWtx7q2D7Y>)

## Problems

* [1192. Critical Connections in a Network (Hard)](https://leetcode.com/problems/critical-connections-in-a-network/)