[Python3] Two very standard Tarjan solutions
One of this code is modified based on [1]https://leetcode.com/problems/critical-connections-in-a-network/discuss/382526/Tarjan-Algorithm-(DFS)-Python-Solution-w
One of this code is modified based on [1]https://leetcode.com/problems/critical-connections-in-a-network/discuss/382526/Tarjan-Algorithm-(DFS)-Python-Solution-with-explanation/358299.\nHowever, [1] is not recording the number of iteration based on the standard Tarjan algorithm. I slightly modified the code and I\'d like to share it here. The code can be understood based on the example shown in the image below, where dfs_num is the number of iteration when the dfs traverse this node. dfs_low is something used to maintain the lowest iteration value (if no cycle, it should be same as the dfs_num, when we have cycles, it will be smaller than dfs_num. This is the key idea why it works.) If you feel it is not easy to understand, search the basic idea about this algorithm online and do it step by step based on the example shown here. It will help.\n![image](https://assets.leetcode.com/users/liketheflower/image_1585620892.png)\nThe above image is from the great book of [competitive programming.](https://www.amazon.com/Competitive-Programming-3rd-Steven-Halim/dp/B00FG8MNN8)\n\nSolution 1 (modified from [1])\n```python\nclass Solution:\n    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n        self.num = 0\n        graph = collections.defaultdict(list)\n        for u, v in connections:\n            graph[u].append(v)\n            graph[v].append(u)\n            \n        dfs_num, dfs_low = [None]*n, [None]*n\n        \n        def dfs(node, parent):\n            # already visited\n            if dfs_num[node] is not None:return \n            dfs_num[node] = dfs_low[node] = self.num\n            self.num += 1\n            for neighbor in graph[node]:\n                if dfs_num[neighbor] is None:\n                    dfs(neighbor, node)\n            \n            # minimal num in the neignbors, exclude the parent\n            dfs_low[node] = min([dfs_low[node]] + [dfs_low[neighbor] for neighbor in graph[node] if neighbor != parent])   \n        \n        dfs(0, None)\n        \n        res = []\n        #print(dfs_num)\n        #print(dfs_low)\n        for u, v in connections:\n            # non bridge\n            if dfs_low[u] > dfs_num[v] or dfs_low[v] > dfs_num[u]:\n                res.append([u, v])\n        return res\n```\nSolution 2 (modified from [2])\n```python\nclass Solution:\n    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n        self.num = 0\n        dfs_num, dfs_low = [None]*n, [None]*n\n        dfs_parents = [None]*n\n        graph = collections.defaultdict(list)\n        for u,v in connections:\n            graph[u].append(v)\n            graph[v].append(u)\n        res = []\n        def dfs(u):\n            dfs_num[u] = dfs_low[u] = self.num\n            self.num += 1\n            for v in graph[u]:\n\t\t\t# unvisited\n                if dfs_num[v] is None:\n                    dfs_parents[v] = u\n                    dfs(v)\n                    if dfs_low[v]>dfs_num[u]:res.append([u,v])\n                    dfs_low[u] = min(dfs_low[u], dfs_low[v])\n\t\t\t\t# visited: update only when v is not parent of u as if we reach this step already means that we are visiting v from u. since uv is undirected, we will have uv vu cycle, this one will not be counted as a TRUE cycle.\n                elif v!=dfs_parents[u]:\n                    dfs_low[u] = min(dfs_low[u], dfs_low[v])\n        for i in range(n):\n            if dfs_num[i] is None:\n                dfs(i)\n        #print(dfs_num)\n        #print(dfs_low)\n        return res                 \n```\nWhen the test case is below, we have the output:\ntest case\n6\n[[0,1],[1,2],[1,3],[1,4],[4,5],[1,5]]\noutput\n[0, 1, 2, 3, 4, 5]\n[0, 1, 2, 3, 1, 1]\n\nThe output of reference[1] code\'s output on this test case is:\n[0, 1, 2, 2, 2, 3]\n[0, 1, 2, 2, 1, 1]\nMore details about different solutions of this problem is summerized here:\nhttps://medium.com/@jim.morris.shen/hard-graph-find-cycles-in-graph-a170810ec142?source=friends_link&sk=f90da551e0b7c7995ae9441524d6fb6f\nThanks for reading.\nReference\n[1]https://leetcode.com/problems/critical-connections-in-a-network/discuss/382526/Tarjan-Algorithm-(DFS)-Python-Solution-with-explanation/358299.\n[2] [competitive programming.](https://www.amazon.com/Competitive-Programming-3rd-Steven-Halim/dp/B00FG8MNN8)
[]