Find Bridges Using Targan's Algorithm

FindBridges.py

# Targan Alog: https://www.youtube.com/watch?v=ZeDNSeilf-Y
# Find Bridges: https://www.youtube.com/watch?v=Rhxs4k6DyMM&t=0s
# Reference: https://gist.github.com/SuryaPratapK/2774cb957a27448b485609418e272f2b
# Find Bridges using Targan Algo

from typing import List, Set, Dict

class Solution():
    def __init__(self) -> None:
        self.timer = 0
        self.discovery = []
        self.low = []
        self.parent = []
        return

    def makeGraph(self, num_nodes: int, connections: List[List[int]]) -> Dict:
        graph = {n: set() for n in range(num_nodes)}
        for x,y in connections:
            graph[x].add(y)
            graph[y].add(x)
        return graph

    def findBridgesUsingTargan(self, graph: Dict, node: int, parent: int):
        self.discovery[node] = self.timer
        self.low[node] = self.timer
        self.timer = self.timer + 1
        self.parent[node] = parent

        for adj_node in graph[node]:
            if self.discovery[adj_node] == -1: # Undiscovered node
                self.findBridgesUsingTargan(graph, adj_node, node)
                self.low[node] = min(self.low[node], self.low[adj_node])
            else:
                if self.parent[node] != adj_node: # Back edge
                    self.low[node] = min(self.low[node], self.discovery[adj_node])
        return

    def run(self, n: int, connections: List[List[int]]) -> List:

        # Init
        bridges = []
        graph = self.makeGraph(n, connections)
        self.discovery = [-1 for _ in range(n)]
        self.low = [-1 for _ in range(n)]
        self.parent = [-1 for _ in range(n)]

        # Run dfs (here it is targan's algo), for all the nodes
        # which are undiscovered
        for i in range(n):
            if self.discovery[i] == -1:
                self.findBridgesUsingTargan(graph, i, i)
        
        # Bridges in a network are those critical connections
        # which when broken creates more than one component in a graph.
        # One way to find the bridge, is to first run the Targan's alog
        # then compare if the low value of the node is greater than the
        # discovery value of its parent. In that case there is no way
        # to reach from that node to its parent or any of the ancestor nodes.
        # Disconnecting any edges from such nodes will divide the graph into
        # more than one connected components.
        for i in range(n):
            if self.low[i] > self.discovery[self.parent[i]]:
                bridges.append([i, self.parent[i]])           
        return bridges


connections = [[0,1], [1,2], [2,0], [0,3], [3,4]]
n = 5
solution = Solution()
print(solution.run(n, connections))