1192. Critical Connections in a Network

Reference: LeetCode
Difficulty: Hard

Problem

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.

Return all critical connections in the network in any order.

Constraints:

• 1 <= n <= 10^5
• n-1 <= connections.length <= 10^5
• connections[i][0] != connections[i][1] (no self-link)
• There are no repeated connections.

Example:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Follow up:

Analysis

Tarjan’s Algorithm

Reference: Java DFS Solution similar to Tarjan, maybe easier to understand

We record the timestamp that we visit each node. For each node, we check every neighbor except its parent and return a smallest timestamp in all its neighbors. If this timestamp is strictly less than the node’s timestamp, we know that this node is somehow in a cycle. Otherwise, this edge from the parent to this node is a critical connection.

int T = 1;

// Assume the graph is connected
public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
  if (n == 0 || connections.size() == 0) {
    return new ArrayList<>();
  }
  // Use a timestamp, check the smallest timestamp that can reach from the node
  // construct the graph first
  List<List<Integer>> graph = new ArrayList<>();
  for (int i = 0; i < n; ++i) {
    graph.add(new ArrayList<Integer>());
  }
  for (List<Integer> conn : connections) {
    graph.get(conn.get(0)).add(conn.get(1));
    graph.get(conn.get(1)).add(conn.get(0));
  }
  
  int [] timestamp = new int[n];
  // for each node, we need to run DFS for it, and return the smallest timestamp in all of its children except its parent
  List<List<Integer>> criticalConns = new ArrayList<>();
  dfs(n, graph, timestamp, 0, -1, criticalConns); // -1 is the parent
  return criticalConns;
}
  
// return the minimum timestamp it every visited in all the neighbors
private int dfs(int n, List<List<Integer>> graph, int[] timestamp, int v, int parent, List<List<Integer>> criticalConns) {
  if (timestamp[v] != 0) { // if a node is visited, its timestamp won't be 0
    return timestamp[v];
  }
  timestamp[v] = T++; // set the node timestamp
  
  // find the node that can be reached with the smallest timestamp
  int minTimestamp = Integer.MAX_VALUE;
  for (int neighbor : graph.get(v)) {
    if (neighbor == parent) continue; // no need to check the parent
    int neighborTimestamp = dfs(n, graph, timestamp, neighbor, v, criticalConns);
    minTimestamp = Math.min(minTimestamp, neighborTimestamp);
  }
  
  // minTimestamp < timestamp[v] --> a cycle
  if (minTimestamp >= timestamp[v]) { // no cycle
    if (parent >= 0) criticalConns.add(Arrays.asList(parent, v));
  }
  return Math.min(timestamp[v], minTimestamp);
}

Time: $O(V + E)$ (connected graph)
Space: $O(V + E)$