[Python] Find all bridges, explained
In my opinion it is very difficult problem if you are not familiar with graph theory. What is actually asked here is to find all so-called bridges in given grap
In my opinion it is very difficult problem if you are not familiar with graph theory. What is actually asked here is to find all so-called **bridges** in given graph, here you can see detailed explanation of the very classical algorithm: https://cp-algorithms.com/graph/bridge-searching.html\n\nHere I give some details about the code, using the link I provided. The key observation about the bridge is:\n\nLet us be at `node` when we use dfs. Then if we have edge `(node, child)`, such that from `child` or any of its descendants we do not have **back edge** (edge which leads to already visited node) to `node` or to some of its ancestors, it means that `(node, child)` is bridge. Indeed, this condition means that there is only one path from `node` to `child`.\n\n1. We use `dfs` with some extra steps to solve this problem. Each time we run `dfs(node, par)`, where `node` is current node we are in and `par` is parent of this node. In the beginning `par` is equal to `-1` means, that we do not have any parent.\n2. We keep global `self.timer` variable: is time of visit of one or another node.\n3. We keep `tin[node]` array, the time when we visit `node`.\n4. Also we keep `fup[node]` array, which will be defined as follow: it is minimum among `tin[node]`: time of visit of `node` and all times of visit for so-called **back edges** and `fup[child]` for all children of `node`. By our definition, `fup[node]` is the smallest time among all descendants of `node`.\n\nThen it can be shown that `(node, child)` is bridge if and only if `fup[child] > tin[node]`.\n\n#### Complexity\nTime complexity is just `O(E + V)` to traverse all graph with dfs and some extra-steps. Space complexity is `O(E + V)` as well to create `graph` and keep `used, tin, fup` arrays.\n\n#### Code\n```\nclass Solution:\n    def criticalConnections(self, n, connections):\n        used, tin, fup = [0]*n, [-1]*n, [-1]*n\n        self.timer, ans = 0, []\n        graph = defaultdict(list)\n        \n        def dfs(node, par = -1):\n            used[node] = 1\n            tin[node] = fup[node] = self.timer + 1\n            self.timer += 1\n            for child in graph[node]:\n                if child == par: continue\n                if used[child] == 1:\n                    fup[node] = min(fup[node], tin[child])\n                else:\n                    dfs(child, node)\n                    fup[node] = min(fup[node], fup[child])\n                    if fup[child] > tin[node]: ans.append([node, child])\n        \n        for i, j in connections:\n            graph[i].append(j)\n            graph[j].append(i)\n            \n        for i in range(n):\n            if not used[i]: dfs(i)\n                \n        return ans\n```
['Graph']