This content originally appeared on DEV Community and was authored by seanpgallivan
This is part of a series of Leetcode solution explanations (index). If you liked this solution or found it useful, please like this post and/or upvote my solution post on Leetcode's forums.
Leetcode Problem #1192 (Hard): Critical Connections in a Network
Description:
(Jump to: Solution Idea || Code: JavaScript | Python | Java | C++)
There are n servers numbered from
0ton-1connected by undirected server-to-server connections forming a network whereconnections[i] = [a, b]represents a connection between serversaandb. Any server can reach any other server directly or indirectly through the network.A critical connection is a connection that, if removed, will make some server unable to reach some other server.
Return all critical connections in the network in any order.
Examples:
Example 1: Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]] Output: [[1,3]] Explanation: [[3,1]] is also accepted. Visual:
Constraints:
1 <= n <= 10^5n-1 <= connections.length <= 10^5connections[i][0] != connections[i][1]- There are no repeated connections.
Idea:
(Jump to: Problem Description || Code: JavaScript | Python | Java | C++)
If 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).
TBFA 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.
To 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.
We'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.
For 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.)
Then 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.
If, after backtracking, the value of low[next] is still higher than low[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).
Once the dfs helper function has completed its traversal, we can return ans.
Implementation:
Javascript strangely runs significantly faster with a regular object rather than a Map().
Javascript Code:
(Jump to: Problem Description || Solution Idea)
var criticalConnections = function(n, connections) {
let edgeMap = {}
for (let i = 0; i < n; i++)
edgeMap[i] = []
for (let [a,b] of connections)
edgeMap[a].push(b), edgeMap[b].push(a)
let disc = new Uint32Array(n), low = new Uint32Array(n),
time = 1, ans = []
const dfs = (curr, prev) => {
disc[curr] = low[curr] = time++
for (let next of edgeMap[curr]) {
if (!disc[next]) {
dfs(next, curr)
low[curr] = Math.min(low[curr], low[next])
} else if (next !== prev)
low[curr] = Math.min(low[curr], disc[next])
if (low[next] > disc[curr])
ans.push([curr, next])
}
}
dfs(0, -1)
return ans
};
Python Code:
(Jump to: Problem Description || Solution Idea)
class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
edgeMap = defaultdict(list)
for a,b in connections:
edgeMap[a].append(b)
edgeMap[b].append(a)
disc, low, time, ans = [0] * n, [0] * n, [1], []
def dfs(curr: int, prev: int):
disc[curr] = low[curr] = time[0]
time[0] += 1
for next in edgeMap[curr]:
if not disc[next]:
dfs(next, curr)
low[curr] = min(low[curr], low[next])
elif next != prev:
low[curr] = min(low[curr], disc[next])
if low[next] > disc[curr]:
ans.append([curr, next])
dfs(0, -1)
return ans
Java Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
int[] disc, low;
int time = 1;
List<List<Integer>> ans = new ArrayList<>();
Map<Integer,List<Integer>> edgeMap = new HashMap<>();
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
disc = new int[n];
low = new int[n];
for (int i = 0; i < n; i++)
edgeMap.put(i, new ArrayList<Integer>());
for (List<Integer> conn : connections) {
edgeMap.get(conn.get(0)).add(conn.get(1));
edgeMap.get(conn.get(1)).add(conn.get(0));
}
dfs(0, -1);
return ans;
}
public void dfs(int curr, int prev) {
disc[curr] = low[curr] = time++;
for (int next : edgeMap.get(curr)) {
if (disc[next] == 0) {
dfs(next, curr);
low[curr] = Math.min(low[curr], low[next]);
} else if (next != prev)
low[curr] = Math.min(low[curr], disc[next]);
if (low[next] > disc[curr])
ans.add(Arrays.asList(curr, next));
}
}
}
C++ Code:
(Jump to: Problem Description || Solution Idea)
class Solution {
public:
vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
disc = vector<int>(n);
low = vector<int>(n);
for (auto conn : connections) {
edgeMap[conn[0]].push_back(conn[1]);
edgeMap[conn[1]].push_back(conn[0]);
}
dfs(0, -1);
return ans;
}
void dfs(int curr, int prev) {
disc[curr] = low[curr] = time++;
for (int next : edgeMap[curr]) {
if (disc[next] == 0) {
dfs(next, curr);
low[curr] = min(low[curr], low[next]);
} else if (next != prev)
low[curr] = min(low[curr], disc[next]);
if (low[next] > disc[curr])
ans.push_back({curr, next});
}
}
private:
vector<int> disc{0}, low{0};
int time = 1;
vector<vector<int>> ans;
unordered_map<int, vector<int>> edgeMap;
};
This content originally appeared on DEV Community and was authored by seanpgallivan
seanpgallivan | Sciencx (2021-04-24T14:17:36+00:00) Solution: Critical Connections in a Network. Retrieved from https://www.scien.cx/2021/04/24/solution-critical-connections-in-a-network/
Please log in to upload a file.
There are no updates yet.
Click the Upload button above to add an update.