Strongly connected components Algo

self containted cycles within a directed graph where every vertext in a given cycle can reach every other vertex in the same cycle

Tarjan's SCC

https://www.youtube.com/watch?v=ZeDNSeilf-Y

Kosaraju Algorithm

https://www.youtube.com/watch?v=Rs6DXyWpWrI

Find Articulation Points

A node is articulations point if on removing it the number of components increases.
Usage
- Find single point of failure in the network and remove it by either adding more edges or redesiging the network.

Tarjan's Algorithm

https://www.youtube.com/watch?v=64KK9K4RpKE&list=RDCMUCnxhETjJtTPs37hOZ7vQ88g&index=3

Problems

https://leetcode.com/discuss/interview-question/436073/

https://leetcode.com/problems/minimize-malware-spread/

https://leetcode.com/problems/minimize-malware-spread-ii/

https://leetcode.com/problems/minimum-number-of-days-to-disconnect-island/

Find Bridges in a graph

A bridge is an edge, removing which increase the number of components.

Tarjan's algo

https://www.youtube.com/watch?v=Rhxs4k6DyMM&list=RDCMUCnxhETjJtTPs37hOZ7vQ88g&index=6

Problems

https://leetcode.com/problems/critical-connections-in-a-network/

https://leetcode.com/problems/redundant-connection/

Reference