There are n servers numbered from 0 to n-1 connected by undirected server-to-server connections forming a network where connections[i] = [a, b] represents a connection between servers a and b. 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.
For example,
Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.
Before going through this solution, I would strongly recommend reading Tarjan’s algorithm and find bridges in a graph problem.
class Solution { int timer; List<List<Integer>> g; boolean [] visited; /* This map stores the time when the current node is visited */ int [] tin; int [] low; void dfs(int u, int parent, List<List<Integer>> res ) { visited[u] = true; //Put the current timer. tin[u] = timer; //Low is the time of entry to start with low[u] = timer; timer++; /* Go through all the neighbors */ for (int to : g.get(u)) { //If it is parent, nothing to be done if (to == parent) continue; /* If the neighbor was already visited get the minimum of the neighbor entry time or the current low of the node. */ if (visited[to]) { low[u] = Math.min(low[u], tin[to]); } else { //Else do the DFS dfs(to, u, res); /* Normal edge scenario, take the minimum of low of the parent and the child. */ low[u] = Math.min(low[u], low[to]); /* If low of the child node is less than time of entry of current node, then there is a bridge. */ if (low[to] > tin[u]){ //List<Integer> l = new ArrayList<>(); List<Integer> l = Arrays.asList(new Integer[]{u, to}); res.add(l); } } } } public void findBridges(List<List<Integer>> res) { timer = 0; for(int i=0; i<g.size(); i++){ if (!visited[i]) dfs(i, -1, res); } } public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) { g = new ArrayList<>(); visited = new boolean[n]; /* This map stores the time when the current node is visited */ tin = new int[n]; low = new int[n]; Arrays.fill(visited, false); Arrays.fill(tin, n); Arrays.fill(low, n); for(int i=0; i<n; i++){ g.add(new ArrayList<>()); } for(List<Integer> l : connections){ g.get(l.get(0)).add(l.get(1)); g.get(l.get(1)).add(l.get(0)); } List<List<Integer>> res = new ArrayList<>(); findBridges(res); return res; } }
The complexity of this code is O(V + E) where V is number of vertices and E is number of edges in the graph.
If you want help with interview preparations, please feel free to book a free demo session with us.