Simple Python Solution | DFS Tarjan's Algorithm | Detailed Comments
\n# Solution 1: DFS with tarjan\'s algorithm. O(n) time and O(n) space complexity\nclass Solution:\n    def criticalConnections(self, n: int, connections: List[
```\n# Solution 1: DFS with tarjan\'s algorithm. O(n) time and O(n) space complexity\nclass Solution:\n    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n        def dfs(current_rank, prev_vertex, current_vertex):\n            # visit the current node\n            visited.add(current_vertex)\n            # update the lowest possible node order that can be gone from this current node\n            # at first it\'s the same as discovery time of the node\n            lowest_rank[current_vertex] = current_rank\n            # now check on the next virtices that are neighbor of the current vertex\n            for next_vertex in graph[current_vertex]:\n                # if it is not the same as the previous vertex from where we have come \n                # to current vertex while DFS\n                if next_vertex != prev_vertex:\n                    # if the vertex not in visited, do dfs on it\n                    # discovery time/rank would be 1 more than the current vertex\n                    if next_vertex not in visited:\n                        dfs(current_rank+1, current_vertex, next_vertex)\n                    # update the rank with the lowest ordered node that can be possible \n                    # to go from this current node\n                    # check the minimum and update if applicable\n                    lowest_rank[current_vertex] = min(lowest_rank[current_vertex], lowest_rank[next_vertex])\n                    # print(next_vertex, current_vertex, lowest_rank[next_vertex], lowest_rank[current_vertex])\n                    # now if the current rank (discovery time) of the current_vertex is less \n                    # than this neighbor vertex means there is no connection for this neighbor \n                    # vertex to another earlier discovered vertex \n                    # without going through this current vertex. So this is a critical connection\n                    # print(current_vertex, next_vertex, current_rank)\n                    if lowest_rank[next_vertex] > current_rank:\n                        result.append([current_vertex, next_vertex])\n        # build the graph            \n        graph = defaultdict(list)\n        for x,y in connections:\n            graph[x].append(y)\n            graph[y].append(x)\n        # print(graph)\n            \n        # hashset for track the visited nodes\n        visited = set()\n        # the first order while DFS, you may think of it as discovery time which starts from 0\n        current_rank = 0\n        # will store the lowest order possible to go from the current node\n        # at first the lowest order is the same as discovery time of the node while dfs\n        lowest_rank = [-1 for i in range(n)]\n        \n        # DFS starts from node number 0 (note that here nodes are numbered from 0 to n-1)\n        # it\'s discovery time/ rank is also 0\n        current_vertex = 0\n        prev_vertex = -1 # a dummy placeholder for previous of starting node.\n        result = [] # will store the reult edges\n        # start dfs on the current vertex. Also provide the rank of it and it\'s previous vertex\n        dfs(current_rank, prev_vertex, current_vertex)\n        # print(result)\n        return result\n        \n        \n        \n\n```
[]