DFS detailed explanation, O(|E|) solution
First thought\n\nThiking for a little while, you will easily find out this theorem on a connected graph:\n\n An edge is a critical connection, if and only if it
## **First thought**\n\nThiking for a little while, you will easily find out this theorem on a connected graph:\n\n* **An edge is a critical connection, if and only if it is not in a cycle.**\n\nSo, if we know how to find cycles, and discard all edges in the cycles, then the remaining connections are a complete collection of critical connections.\n\n----\n\n## **How to find eges in cycles, and remove them**\n\nWe will use DFS algorithm to find cycles and decide whether or not an edge is in a cycle.\n\nDefine **rank** of a node: The depth of a node during a DFS. The starting node has a *rank* 0.\n\nOnly the nodes on the current DFS path have non-special *ranks*. In other words, only the nodes that we\'ve started visiting, but haven\'t finished visiting, have *ranks*. So `0 <= rank < n`.\n\n(For coding purpose, if a node is not visited yet, it has a special rank `-2`; if we\'ve fully completed the visit of a node, it has a special rank `n`.)\n\n**How can "rank" help us with removing cycles?** Imagine you have a current path of length `k` during a DFS. The nodes on the path has increasing ranks from `0` to `k`and incrementing by `1`. Surprisingly, your next visit finds a node that has a rank of `p` where `0 <= p < k`. Why does it happen? Aha! You found a node that is on the current search path! That means, congratulations, you found a cycle!\n\nBut only the current level of search knows it finds a cycle. How does the upper level of search knows, if you backtrack? Let\'s make use of the return value of DFS: **`dfs` function returns the minimum rank it finds.** During a step of search from node `u` to its neighbor `v`, **if `dfs(v)` returns something smaller than or equal to `rank(u)`**, then `u` knows its neighbor `v` helped it to find a cycle back to `u` or `u`\'s ancestor. So `u` knows it should discard the edge `(u, v)` which is in a cycle.\n\nAfter doing dfs on all nodes, all edges in cycles are discarded. So the remaining edges are critical connections.\n\n----\n\n## **Python code**\n\n```\nimport collections\nclass Solution(object):\n    def criticalConnections(self, n, connections):\n        def makeGraph(connections):\n            graph = collections.defaultdict(list)\n            for conn in connections:\n                graph[conn[0]].append(conn[1])\n                graph[conn[1]].append(conn[0])\n            return graph\n\n        graph = makeGraph(connections)\n        connections = set(map(tuple, (map(sorted, connections))))\n        rank = [-2] * n\n\n        def dfs(node, depth):\n            if rank[node] >= 0:\n                # visiting (0<=rank<n), or visited (rank=n)\n                return rank[node]\n            rank[node] = depth\n            min_back_depth = n\n            for neighbor in graph[node]:\n                if rank[neighbor] == depth - 1:\n                    continue  # don\'t immmediately go back to parent. that\'s why i didn\'t choose -1 as the special value, in case depth==0.\n                back_depth = dfs(neighbor, depth + 1)\n                if back_depth <= depth:\n                    connections.discard(tuple(sorted((node, neighbor))))\n                min_back_depth = min(min_back_depth, back_depth)\n            rank[node] = n  # this line is not necessary. see the "brain teaser" section below\n            return min_back_depth\n            \n        dfs(0, 0)  # since this is a connected graph, we don\'t have to loop over all nodes.\n        return list(connections)\n```\n\n----\n\n## **Complexity analysis**\nDFS time complexity is O(|E| + |V|), attempting to visit each edge at most twice. (the second attempt will immediately return.)\nAs the graph is always a connected graph, |E| >= |V|.\n\nSo, time complexity = O(|E|).\n\nSpace complexity = O(graph) + O(rank) + O(connections) = 3 * O(|E| + |V|) = O(|E|).\n\n----\n\n## **FAQ: Are you reinventing Tarjan?**\nHonestly, I didn\'t know Tarjan beforehand. The idea of using `rank` is inspired by [preordering](https://en.wikipedia.org/wiki/Depth-first_search#Vertex_orderings) which is a basic concept of DFS. Now I realize they are similar, but there are still major differences between them.\n\n* This solution uses only one array `rank`. While Tarjan uses two arrays: `dfn` and `low`.\n* This solution\'s `min_back_depth` is similar to Tarjan\'s `low`, but `rank` is very different than `dfn`. `max(dfn)` is always n-1, while `max(rank)` could be smaller than n-1.\n* This solution construsts the result by removing non-critical edges **during** the dfs, while Tarjan constructs the result by collecting non-critical edges **after** the dfs.\n* In this solution, only nodes actively in the current search path have `0<=rank[node]<n`; while in Tarjan, nodes not actively in the current search path may still have `0<=dfn[node]<=low[node]<n`.\n\n----\n\n## **Brain teaser**\n\nThanks [@migfulcrum](https://leetcode.com/migfulcrum) for [pointing out](https://leetcode.com/discuss/comment/359567) that `rank[node] = n` is not necessary. He is totally right. I\'ll leave this as a brain teaser for you: why is it not necessary?\n(Hint: after we\'ve finished visiting a node, is it possible to have another search path attempting to visit this node again?)\n\n----\n\n(If you like this post, don\'t forget to vote up so more people will read it!)
[]