Cleanest and Easiest Understand Python Solution - 99% Time, 100% Mem
[No \'RANK\', DEPTH is ENOUGH]\n\nYou might see many solutions suggest to track something called "rank" which is usually defined as the order of a DFS/BFS searc
**[No \'RANK\', DEPTH is ENOUGH]**\n\nYou might see many solutions suggest to track something called "rank" which is usually defined as the order of a DFS/BFS search. It\'s confusing. I spent some time understanding this question, and hope my understanding can save you some time.\n\nIn this question, we only need to keep track of the **minimum reachable depth** of a node. Because for a node "u", if the returned **minimum reachable depth** of it\'s neighbor "v" is strictly larger than the **minimum reachable depth** of itself, then (u, v) is a critical edge.\n\nThe only caveat is that the definifition of "**minimum reachable depth**" is slightly tricky, which will not be overided by forward propagation but can be overided by backtracking because of cycles.\n\nFor example, if the depth of node "u" is 0 and node "v" is an unexplored neighbor of "u", then we should first update "v" with depth=1 by walking DFS/BFS from u to v (direct connection). However, if "u" and "v" are in a big cycle, the depth of "u", which is 0 will be propageted to "v" by other edges, so in the end, "v" will have a **minimum reachable depth** equals to 0, and (u,v) is not a critical connection. Here, you can also see that if such cycles do not exist, then "u" would have depth 0 and "v" would still have depth 1, so (u,v) is a critical connection.\n\n***NOTE: The initial **DPETH** of a node obtained by DFS/BFS (forward propagation) is the  **Minimum Reachable Depth** if no backtracking (i.e. no cycle) occurred.\n\n[Illustration of example-1]\n\n         u\n\t\t/  \\     , Assume we start DFS from \'u\' whose depth is 0, and at the first step we walk from \'u\' to \'v\', we will update depth of \'v\' to 1. Then, we walk from \'v\' to \'m\', and update depth of \'m\' to 2. \n       m  - v      Finally, we walk from \'m\' to \'u\' and see it has been reached with depth equals to 0 (which I called \'minimum depth earlier\'), we backtrack the depth of \'m\' to 0, and thus backtrack the depth of \'v\' to 0.\n\t\t           Because all the nodes have the minimum reachable depths equal to 0, no depth is strictly larger than others, therefore, all the 3 connections are not critical edge. \n\t\t\t\t   \n[Illustration of example-2]\n\n         u\n\t\t/  \\     , Following from the previous example we know that if we start DFS from node \'u\', in the end nodes \'u\', \'v\', \'m\' would have a minimum reachable depths equal to 0.\n       m  - v      But, \'n\' will have a depth of \'2\'. why it is not updated through backtracking? Because the depth of n is originall propagated through m, and when DFS reached \'n\' the search of that branck is stopped.\n\t  /            When the depth 0 is backtracking from \'u\' to \'m\' and to \'v\', this backtracking would not go through m->n again! (This is the forward propagate of the original DFS!), so the depth of n remains 2.\n\t n          Finally we see that (m,n) is a critical connection.\n\t\t\t\t  \nI hope the code is simple enough to explain itself. Please feel free to leave any comment if this still confuses you.\n\n```\nclass Solution(object):\n    def criticalConnections(self, n, connections):\n        # graph construction\n        graph = [[] for i in range(n)]\n        for u, v in connections:\n            graph[u].append(v)\n            graph[v].append(u)\n        \n        # depth initialization\n        depths = [-1] * n\n        results = []\n        \n        """\n        visit every node exactly once, the starting point does not matter\n        (as long as graph is connected)\n        """\n        def dfs(prev_node, cur_node, cur_depth):\n            depths[cur_node] = cur_depth\n            min_depth = cur_depth\n            for neighbor in graph[cur_node]:\n                if neighbor == prev_node: continue\n                """\n                find the temporary depth reached by a neighbor\n                """\n                temp_depth = depths[neighbor]\n\t\t\t\t"""\n\t\t\t\tif the node is unexplored,  assign it\'s depth to current depth + 1\n\t\t\t\t"""\n                if temp_depth == -1:\n                    temp_depth = dfs(cur_node, neighbor, cur_depth+1)\n                """\n                if the returned depth is deeper than the "current depth", then it is a critical connection\n                else, update the min_depth\n\t\t\t\tNOTE: we are comparing the "returned depth from neighbor (temp_dpeth)" to the "current depth reached by DFS" rather than the "min_depth" that is going to be returned.\n\t\t\t\t\tbecause once the temp_depth is returned by a neighbor, it is the minimum depth of it. \n                """\n                if temp_depth > cur_depth:\n                    results.append([cur_node, neighbor])\n                else:\n                    min_depth = min(min_depth, temp_depth)\n            """\n            return the minimum depth reached by a node\n            """\n            depths[cur_node] = min_depth\n            return min_depth\n        \n        # start at node-0\n        dfs(None, 0, 0)\n        \n        return results\n        \n```
[]