Python DFS-Tree Solution (O(V+E) complexity)
Codes written in weekly contest, heavily inspired by gfg (https://www.geeksforgeeks.org/bridge-in-a-graph/) and the Amazon OA discussion thread (https://leetcod
Codes written in weekly contest, heavily inspired by gfg (https://www.geeksforgeeks.org/bridge-in-a-graph/) and the Amazon OA discussion thread (https://leetcode.com/discuss/interview-question/372581), especially @ramyarao - Thank you for your detailed explanation in your comment under that discussion thread, and my code is mostly a Python3 version with "lowest" update in my own way.\n\nThe basic idea is: keep a DFS tree and related informations:\n1. visited: whether the node has been visited or not.\n2. parent: the parent-child relationship in the dfs tree. We certainly do not want to go backwards on an edge which has already been checked earlier.\n3. depth: the "depth" of each node in the DFS tree. It\'s the "sequence number" of nodes we visit rather than the actual depth, keep that in mind.\n4. lowest: the lowest (in terms of sequence number/depth) node we can visit though the subtree of the node. This is the key part: if we can visit lower (close to the top) nodes through (parent, child) than parent itself, it means child is accessible in at least \ntwo routes, and hence (u,v) is not a cricital edge (and vise versa).\n\nFor each node (u), we check all its children (v): if v has not been visited, we recursively call the find() function to v (to retrieve needed information). If lowest[v]>lowest[u], we know that (u,v) is a critical edge and output it. Besides, if v is the parent of u, it means in the DFS tree u comes from v (v->u) so we shouldn\'t update u\'s information based on v. Otherwise, we update lowest[u] with min(lowest[u], lowest[v]) since v is part of the subtree of u.\n\nCodes attached:\n```\nclass Solution:\n    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n        \n        dic = collections.defaultdict(list)\n        for c in connections:\n            u, v = c\n            dic[u].append(v)\n            dic[v].append(u)\n            \n        \n        timer = 0\n        \n        depth, lowest, parent, visited = [float("inf")]*n, [float("inf")]*n, [float("inf")]*n, [False]*n\n        res = []\n        \n        def find(u):\n            \n            nonlocal timer\n            \n            visited[u] = True\n            depth[u], lowest[u] = timer, timer\n            timer += 1\n            \n            for v in dic[u]:   \n                \n                if not visited[v]:\n                    parent[v] = u\n                    find(v)\n                    if lowest[v]>depth[u]:\n                        res.append([u,v])\n                \n                if parent[u]!=v:\n                    lowest[u] = min(lowest[u], lowest[v])\n                \n        find(0)\n        return res\n        \n```\n
['Tree', 'Depth-First Search', 'Python3']