Critical Connections in a Network | JS, Python, Java, C++ | Tarjan's Algorithm Solution w/ Explan.
(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful, please upvote this post.)\n\n---\n\n#### Idea:\n
*(Note: This is part of a series of Leetcode solution explanations. If you like this solution or find it useful,* ***please upvote*** *this post.)*\n\n---\n\n#### ***Idea:***\n\nIf we think of the network and its connections like an undirected graph and its edges, then a critical connection, as defined by this problem, is the same as a bridge in the graph. To find out which edges are bridges, we can employ **Tarjan\'s Bridge-Finding Algorithm** (**TBFA**).\n\nTBFA is a bit like a combination of a **depth-first search** (**DFS**) approach with **recursion** and a **union-find**. IN TBFA, we do a recursive DFS on our graph and for each node we keep track of the earliest node that we can circle back around to reach. By doing this, we can identify whether a given edge is a bridge because the far node doesn\'t lead back to any other earlier node.\n\nTo implement our TBFA, the first thing we have to do is to construct an **edge map** (**edgeMap**) from the **connections** list. Each key in our edge map should correspond to a specific node, and its value should be an array of each adjacent node to the key node.\n\nWe\'ll also need separate arrays to store the discovery time (**disc**) and the lowest future node (**low**) for each node, as well as a **time** counter to use with **disc**.\n\nFor our recursive DFS helper (**dfs**), each newly-visited node should set its initial value for both **disc** and **low** to the current value of **time** before **time** is incremented. (_Note: If we start **time** at **1** instead of **0**, we can use either **disc** or **low** as a visited array, rather than having to keep a separate array for the purpose. Any non-zero value in the chosen array will then represent a visited state for the given node._)\n\nThen we recursively call **dfs** on each of the unvisited adjacent nodes (**next**) of the current node (**curr**). If one of the possible **next** nodes is an earlier node (**disc[next] < curr[low]**), then we\'ve found a loop and we should update the **low** value for the current node. As each layer of the recursive function backtracks, it will propagate this value of **low** back down the chain.\n\nIf, after backtracking, the value of **low[next]** is still higher than **disc[curr]**, then there is no looped connection, meaning that the edge between **curr** and **next** is a bridge, so we should add it to our answer array (**ans**).\n\nOnce the **dfs** helper function has completed its traversal, we can **return ans**.\n\n---\n\n#### ***Implementation:***\n\nJavascript strangely runs significantly faster with a regular object rather than a **Map()**.\n\n---\n\n#### ***Javascript Code:***\n\nThe best result for the code below is **652ms / 106.0MB** (beats 100% / 78%).\n```javascript\nvar criticalConnections = function(n, connections) {\n    let edgeMap = {}\n    for (let i = 0; i < n; i++)\n        edgeMap[i] = []\n    for (let [a,b] of connections)\n        edgeMap[a].push(b), edgeMap[b].push(a)\n    let disc = new Uint32Array(n), low = new Uint32Array(n),\n        time = 1, ans = []\n    const dfs = (curr, prev) => {\n        disc[curr] = low[curr] = time++\n        for (let next of edgeMap[curr]) {\n            if (!disc[next]) {\n                dfs(next, curr)\n                low[curr] = Math.min(low[curr], low[next])\n            } else if (next !== prev)\n                low[curr] = Math.min(low[curr], disc[next])\n            if (low[next] > disc[curr])\n                ans.push([curr, next])\n        }\n    }\n    dfs(0, -1)\n    return ans\n};\n```\n\n---\n\n#### ***Python Code:***\n\nThe best result for the code below is **2248ms / 85.9MB** (beats 79% / 69%).\n```python\nclass Solution:\n    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:\n        edgeMap = defaultdict(list)\n        for a,b in connections:\n            edgeMap[a].append(b)\n            edgeMap[b].append(a)\n        disc, low, time, ans = [0] * n, [0] * n, [1], []\n        def dfs(curr: int, prev: int):\n            disc[curr] = low[curr] = time[0]\n            time[0] += 1\n            for next in edgeMap[curr]:\n                if not disc[next]:\n                    dfs(next, curr)\n                    low[curr] = min(low[curr], low[next])\n                elif next != prev:\n                    low[curr] = min(low[curr], disc[next])\n                if low[next] > disc[curr]:\n                    ans.append([curr, next])\n        dfs(0, -1)\n        return ans\n```\n\n---\n\n#### ***Java Code:***\n\nThe best result for the code below is **130ms / 94.2MB** (beats 57% / 98%).\n```java\nclass Solution {\n    int[] disc, low;\n    int time = 1;\n    List<List<Integer>> ans = new ArrayList<>();\n    Map<Integer,List<Integer>> edgeMap = new HashMap<>();\n    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {\n        disc = new int[n];\n        low = new int[n];\n        for (int i = 0; i < n; i++)\n            edgeMap.put(i, new ArrayList<Integer>());\n        for (List<Integer> conn : connections) {\n            edgeMap.get(conn.get(0)).add(conn.get(1));\n            edgeMap.get(conn.get(1)).add(conn.get(0));\n        }\n        dfs(0, -1);\n        return ans;\n    }\n    public void dfs(int curr, int prev) {\n        disc[curr] = low[curr] = time++;\n        for (int next : edgeMap.get(curr)) {\n            if (disc[next] == 0) {\n                dfs(next, curr);\n                low[curr] = Math.min(low[curr], low[next]);\n            } else if (next != prev)\n                low[curr] = Math.min(low[curr], disc[next]);\n            if (low[next] > disc[curr]) \n                ans.add(Arrays.asList(curr, next));\n        }\n    }\n}\n```\n\n---\n\n#### ***C++ Code:***\n\nThe best result for the code below is **652ms / 210.3MB** (beats 32% / 16%).\n```c++\nclass Solution {\npublic:\n    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {\n        disc = vector<int>(n);\n        low = vector<int>(n);\n        for (auto conn : connections) {\n            edgeMap[conn[0]].push_back(conn[1]);\n            edgeMap[conn[1]].push_back(conn[0]);\n        }\n        dfs(0, -1);\n        return ans;\n    }\n    void dfs(int curr, int prev) {\n        disc[curr] = low[curr] = time++;\n        for (int next : edgeMap[curr]) {\n            if (disc[next] == 0) {\n                dfs(next, curr);\n                low[curr] = min(low[curr], low[next]);\n            } else if (next != prev)\n                low[curr] = min(low[curr], disc[next]);\n            if (low[next] > disc[curr]) \n                ans.push_back({curr, next});\n        }\n    }\nprivate:\n    vector<int> disc{0}, low{0};\n    int time = 1;\n    vector<vector<int>> ans;\n    unordered_map<int, vector<int>> edgeMap;\n};\n```
[]