[Python] Find bridges/articulation points with detailed explanation
FIND BRIDGES IN CONNECTED UNDIRECTED GRAPH #\n1. Brute force O(E)O(E+V) - TLE 8/12\n- Iterate over the edges, remove an edge and run a DFS on the remaining grap
# FIND BRIDGES IN CONNECTED UNDIRECTED GRAPH #\n**1. Brute force O(E)O(E+V) - TLE 8/12**\n- Iterate over the edges, remove an edge and run a DFS on the remaining graph (exclusing the edge you just removed) to see whether you\'d still be able to traverse the entrie graph. If (len(visited) != number of nodes), the removed edge is a bridge.\n \n- Notice that the brute force method, despite being slow, works when the goal is detecting critical connections (bridges). However, it doesn\'t work when detecting redundant connections. See [684.Redundant Connections](https://leetcode.com/problems/redundant-connection/)  (why?) See explanation [here](https://leetcode.com/problems/redundant-connection/discuss/353885/Possible-wrong-test-casehttp://)\n\n```\n def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n        \'\'\'\n        Brute force - O(E)*O(E+V) = O(E^2 + V)\n        \'\'\'\n        from collections import defaultdict\n        critical_conn = []\n        for conn in connections:\n            removed_edge = conn\n            # print(\'-- new edge has been removed --\', removed_edge)\n            d = defaultdict(list)\n            for conn in connections:\n                if conn != removed_edge:\n                    k, v = conn\n                    d[k].append(v)\n                    d[v].append(k) # unidrected\n                \n            stack = [list(d.keys())[0]]\n            visited = set()\n            while stack:\n                node = stack.pop()\n                # print(\'node = \', node)\n                visited.add(node)\n                for nei in d[node]:\n                    if nei not in visited:\n                        stack.append(nei)\n                #         d[nei].remove(node)\n                # del d[node]\n            if len(visited) != n:\n                critical_conn.append(removed_edge)\n        return critical_conn\n```\n\n\n**2. Linear Time O(E+V)**\n\n- The kinear time Algorithm in a nutshell is nothing but your regular DFS with some extra book-keeping to detect the back-edges that take place as you perform the DFS traversal (in other words the backedges that form in your DFS traversal tree).\n \n- **Why do we wanna detect backedges you ask? And how would that help me in finding bridges?** \nConsider an edge:  ```node ---> nei ``` , this edge would be a bridge (aka a critical connection if and only if ```nei``` has no other means of connecting back to the graph except through that edge. If that edge is cut, then ```nei``` is disconnected from the graph. On the other hand, if we can find a backedge from ```nei``` to an anscestor of ```node```, this means ```nei``` is connected to the graph through some other means and thus, the edge ```node --> nei``` is not a bridge.- \n- **How do we know if there is a backedge?**\nAs we run our DFS, we keep track of two things:``` id``` and ```lowest id```. The id is nothing but the time of entry with respect to all the nodes in the graph. And ```lowest id``` is the lowest id of all the reachable neighbours from that node. Thus if ```id of a node < lowest id of all reachable nodes of nei```, this means there was no backedge from nei to an anscestor of node and thus (node -> nei) is a bridge.\n\n\n**1. Declaring res, visited, low, stack as class attributes**\n- self.res = []\n- self.visited = set()\n- self.low = {}\n- self.stack = []\n\n```\ndef dfs(self,id,prevNode, node):\n\t# recursive - dfs with an implicit stack\n\tself.visited.add(node)\n\tself.low[node] = id # ----- initially set the low-link value = id\n\n\tfor nei in self.d[node]:\n\t\tif nei == prevNode:\n\t\t\tcontinue # --------  (I) \n\n\t\tif nei not in self.visited:\n\t\t\tself.dfs(id+1, node, nei) # -- propogate to neighbours\n\n\t\tself.low[node] = min(self.low[node], self.low[nei])  # --- (II)\n\t\tif id < self.low[nei]: # --- Bridge found --- (III)\n\t\t\tself.res.append([node, nei])\n\t\t\t\t\n def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n\t# Build the graph:\n\tfrom collections import defaultdict\n\tself.d = defaultdict(list)\n\tfor k, v in connections:\n\t\tself.d[k].append(v)\n\t\tself.d[v].append(k) # undirected\n\n\tself.res = []\n\tself.visited = set()\n\tself.low = {}\n\n\tself.dfs(0, -1, 0) \n\treturn self.res\n\n#  I:\n# Skip parent - go find an indirect link.\n# Since this is an undirected graph, there is bound to be an edge that directly links to the node we were just at previosuly.\n# Which is something we want to avoid. Instead, what we want to do is investaigate whether or not there is an indirect link that takes \n# us back to a previous node. In short, we are forcing the DFS algorithm to go see all the other neighbours and skip the previous \n# parent node - and go find an indirect route. This is necessary for \n\n\n#  II: \n# As long as there exists nodes that are reachable from where I am, and those nodes have lower ids, \n# keep minimizing the lowest rank of your current node. This usually occues when there\'s a cycle. \n\n# III:\n# If there was a bridge, then the lowest rank of the node you\'re going to would at least be as low as the node we started from.\n\n# Note:\n\t# - The same algorithm can be used to:\n\t\t# - Detect cycles in di-graphs - in addition to the topological sort algortihm\n\t\t# - Can also detect cycles in undirected graphs - but would be an overkill. A simple dfs and maintaing a visited would do.\n```\n\n\n**2. Passing res, visited, low, stack as arguments to the recursive helper function**\n- dfs(self,id,prevNode, node, res, visited, low, stack, d)\n\n```\ndef dfs(self,id,prevNode, node, res, visited, low, stack, d):\n\t# recursive - dfs with an implicit stack\n\tvisited.add(node)\n\tlow[node] = id # ----- initially set the low-link value = id\n\n\tfor nei in d[node]:\n\t\tif nei == prevNode:\n\t\t\tcontinue # -------- skip parent - go find an indirect link\n\n\t\tif nei not in visited:\n\t\t\tdfs(id+1, node, nei, res, visited, low, stack, d) \n\n\t\tlow[node] = min(low[node], low[nei])\n\t\tif id < low[nei]: # --- Bridge found\n\t\t\tres.append([node, nei])\n\t\t\t\t\n def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n\t# Build the graph:\n\tfrom collections import defaultdict\n\td = defaultdict(list)\n\tfor k, v in connections:\n\t\td[k].append(v)\n\t\td[v].append(k) # undirected\n\n\tres = []\n\tvisited = set()\n\tlow = {}\n\n\tself.dfs(0, -1, 0) \n\treturn res\n```\n\n**3. A failed attempt at an Iterative approach - using an explicit stack**\n- Won\'t work. Why? See comment below\n- Low[nei] will casue a key error because unlike the recursive approach, the algorithm here will visit the nodes in the order of their id\n- The recursive nature is important because it propogates to the neighbours first and then takes care of the current node.\n- This is necessary because the low-link values of the neighbours are needed to process the node.\n\n```\ndef dfs(self,id,prevNode, node):\n\tself.stack = [(id, node, prevNode)\n\twhile stack:\n\t\tnode = stack.pop()\n\t\tself.visited.add(node)\n\t\tself.low[node] = id # ----- initially set the low-link value = id\n\n\t\tfor nei in self.d[node]:\n\t\t\tif nei == prevNode:\n\t\t\t\tcontinue # -------- skip parent - go find an indirect link\n\n\t\t\tif nei not in self.visited:\n\t\t\t\tself.stack.append((id+1, nei, node))\n\n\t\t\tself.low[node] = min(self.low[node], self.low[nei])    # ----- low[nei] will cause a key error\n\t\t\tif id < self.low[nei]: # --- Bridge found\n\t\t\t\tself.res.append([node, nei])\n```\n\n\n**Reference:**\nCheck out this amazing video for further understanding\nhttps://www.youtube.com/watch?v=aZXi1unBdJA&t=847s\n\n.\n.\n# FIND CUT-VERTICIES IN CONNECTED UNDIRECTED GRAPH\n\n```\ndef find_articulation_points(edges):\n   \n    # build graph:\n    from collections import defaultdict\n    d = defaultdict(list)\n    for k, v in edges:\n        d[k].append(v)\n        d[v].append(k) # undirected\n    \n    visited = set()\n    art = set()\n    parents = {} # -- ***********\n    low = {} # - where we store the lowest id reachable \n    # (in simpler words, trying to detect the backedge in the DFS spanning tree)\n    # detecting the backedge is the crux if this problem\n    # and so many other problems actually:\n        # - critical edge (bridge)\n        # - critical node (cut-vertex)(articulation point)\n        # - detecting a cycle (directed and undirected)\n\n    # helper dfs #\n    def dfs(id, node, parent):\n        visited.add(node)\n        parents[node] = parent # -- ***********\n        numEdges = 0\n        low[node] = id\n\n        for nei in d[node]:\n            if nei == parent:\n                continue\n            if nei not in visited:\n                parents[nei] = node # -- case B\n                numEdges += 1       # -- case B\n                dfs(id+1, nei, node) # - propogate\n            \n            low[node] = min(low[node], low[nei])\n\n            if id <= low[nei]: # - case A\n                if parents[node] != -1: # - must not be root\n                    art.add(node)\n\n        \n        if (parents[node] == -1 and numEdges >= 2): # if root - different condition applies\n            art.add(node)\n\n    dfs(0, 0, -1) # id, node(root), parent\n    return art\n\n```\n\n**Resources:**\n- Check out Abdul Bari\'s video\nhttps://www.youtube.com/watch?v=jFZsDDB0-vo\n\n- Tushar\nhttps://github.com/mission-peace/interview/blob/master/src/com/interview/graph/ArticulationPoint.java#L79\n\n- 5.9.2 Articulation Vertices - **The Algorithm Design Manual by Steven S Skiena**\n\n- Note that linear solution is only possible when input graph is connected\nif graph is disconnected, we have to have an outer loop O(E^2 + V)\n\n**Summary**\n![image](https://assets.leetcode.com/users/1961/image_1581634887.png)\n\n**Note:**\n\nIf you\'re interested in knowing the reason as to why each articulation point was deteced, you can make your code more explicit in order to detect why your code thinks an articulation node should be considered as such. See below:\n\n```\nfor nei in d[node]:\n            if nei == parent:\n                continue\n\n            if nei not in visited:\n                parents[nei] = node\n                numEdges += 1\n                dfs(nei, node, id+1)\n            \n            low[node] = min(low[node], low[nei]) # - whether neigh seen before or not\n\n            if id < low[nei]:           # --------------------------------------- cut-vertex due to bridge\n                if parents[node] != -1: # not a root\n                    res.add((node, "bridge"))\n            \n            if id == low[nei]:        # --------------------------------------- cut-vertex due to cycle\n                if parents[node] != -1: # not a root\n                    res.add((node, "cycle"))\n        \n        if parents[node] == -1 and numEdges >= 2:\n            res.add((node, "root"))   # ----------------------------------- cut-vertex due to root\n```\n\nExample1:\n```\nedges =  [[0, 1], [0, 2], [1, 3], [2, 3], [2, 5], [5, 6], [3, 4]]\n{(5, \'bridge\'), (3, \'bridge\'), (2, \'bridge\')}\n```\n\nExample2:\n```\nedges = 5, 5, [[1,0], [0,2], [2,1], [0,3], [3,4]]\n{(3, \'bridge\'), (0, \'root\')}\n```\n\nExample3:\n```\nedges = [[0,1], [1,2], [2,3]]\n{(2, \'bridge\'), (1, \'bridge\')}\n```\n\nExample4:\n```\nedges = [[0,1], [1,2], [2,0], [1,3], [1,4], [1,6], [3,5], [4,5]]\n{(1, \'bridge\')}\n```\n\n\n\n**Does this algorithm work for random root? Or nodes that are not integers?**\n\nWhat if the nodes are not integers, for ex "A", "B", "C", ... or what if we want to start the algorithm from a random node as our root (not necessirly node 0)\nThe algorithm still works for a random starting node and also for nodes that are not integers. This can be done by introdicing a small modification. Use a flag to mark whether or not a node is a root as show below:\n\n```\ndef findArtPoints_3(edges):\n    # helper recursive dfs:\n    def dfs(node, parent, id):\n        visited.add(node)\n        parents[node] = parent\n        low[node] = id\n        numEdges = 0\n        isRoot = False\n        if parent == -1:       # ---------- Use a flag\n            isRoot = True\n\n        for nei in d[node]:\n            if nei == parent:\n                continue\n            if nei not in visited:\n                parents[nei] = node\n                numEdges += 1\n                dfs(nei, node, id+1)\n            \n            low[node] = min(low[node], low[nei])\n            if id < low[nei]: # - bridge\n                if not isRoot:      # ---------- Use a flag\n                    res.append(node)\n            if id == low[nei]: # - cycle\n                if not isRoot:    # ---------- Use a flag\n                    res.append(node)\n\n        if isRoot and numEdges >= 2:   # ---------- Use a flag\n            return res\n\n\n    # Build graph:\n    from collections import defaultdict\n    d = defaultdict(list)\n    for k, v in edges:\n        d[k].append(v)\n        d[v].append(k)\n    \n    visited = set()\n    parents = {}\n    low = {}\n    res = []\n\n    rndm_root = edges[0][0]\n    dfs(rndm_root, -1, 0)\n    return res\n```
[]