hard Critical Connections in a Network

Problem Statement

You are given n servers numbered from 0 to n-1, connected by some number of undirected connections where connections[i] = [ai, bi] represents a connection between servers ai and bi. Any server can reach other servers directly or indirectly through the network.

A critical connection is a connection that, if removed, will make some servers unable to reach some other servers.

Return all critical connections in the network.

Examples

Example 1:

• Input: n = 5, connections = [[0, 1], [1, 2], [2, 3], [3, 4], [2, 4]]
• Expected Output: [[1,2],[0,1]]

• Justification: Removing either [0, 1] or [1, 2] will split the network into separate parts, making some servers unreachable from others.

Example 2:

• Input: n = 4, connections = [[0, 1], [0, 2], [1, 2], [2, 3]]
• Expected Output: [[2, 3]]

• Justification: Removing [2, 3] will isolate server 3, making it unreachable from the other servers.

Example 3:

• Input: n = 6, connections = [[0, 1], [1, 2], [2, 0], [1, 3], [3, 4], [4, 5], [5, 3]]
• Expected Output: [[1, 3]]

• Justification: Removing [1, 3] will disconnect servers 3, 4, and 5 from the rest of the network.

Constraints:

• 2 <= n <= 10⁵
• n - 1 <= connections.length <= 10⁵
• 0 <= a_i, b_i <= n - 1
• a_i != b_i
• There are no repeated connections.

Solution

To solve this problem, we can use Depth First Search (DFS). The key idea is to identify bridges in the graph. A bridge is an edge that, when removed, splits the graph into disconnected parts. By using DFS, we can record the discovery and low-link values of each node. The discovery time is the time at which a node is first visited, and the low-link value is the smallest discovery time reachable from the node. If a node cannot reach an ancestor node through its descendants, then the edge leading to that descendant is a critical connection.

This approach is effective because it systematically explores all nodes and edges using DFS, ensuring that all potential critical connections are examined. The use of discovery and low-link values helps in efficiently identifying critical connections with a time complexity of , where V is the number of nodes and E is the number of edges.

Step-by-Step Algorithm

1. Initialize Data Structures:

   • Create an adjacency list graph to represent the network of servers.
   • Create arrays disc and low to store the discovery times and the lowest discovery times reachable for each node, initialized to -1.
   • Initialize a list res to store the critical connections.
   • Set a global time variable to track the discovery time during DFS.

2. Build the Graph:

   • For each connection [u, v] in connections, add v to the adjacency list of u and u to the adjacency list of v.

3. DFS Function:

   • Define a recursive DFS function that takes the current node u, its parent node parent, the disc, low, graph, and res as arguments.
   • Set disc[u] and low[u] to the current time, then increment time.
   • For each neighbor v of u in the graph:
     • If v is the parent of u, skip it.
     • If v has not been visited (disc[v] == -1):
       • Recursively call DFS on v with u as the parent.
       • Update low[u] to the minimum of low[u] and low[v].
       • If low[v] > disc[u], add [u, v] to res as it is a critical connection.
     • If v has already been visited and is not the parent, update low[u] to the minimum of low[u] and disc[v].

4. Run DFS:

   • Call the DFS function starting from node 0 with -1 as the parent.

5. Return Result:

   • Return the list res containing all the critical connections.

Algorithm Walkthrough

Let's walk through the algorithm with n = 5 and connections = [[0, 1], [1, 2], [2, 3], [3, 4], [2, 4]].

1. Initialize Data Structures:

   • graph = [[], [], [], [], []]
   • disc = [-1, -1, -1, -1, -1]
   • low = [-1, -1, -1, -1, -1]
   • res = []
   • time = 0

2. Build the Graph:

   • After processing connections:
     • graph = [[1], [0, 2], [1, 3, 4], [2, 4], [3, 2]]

3. Run DFS starting from node 0:

   • DFS on node 0:

     • disc[0] = 0, low[0] = 0, time = 1
     • Visit neighbor 1.

   • DFS on node 1:

     • disc[1] = 1, low[1] = 1, time = 2
     • Skip neighbor 0 (parent).
     • Visit neighbor 2.

   • DFS on node 2:

     • disc[2] = 2, low[2] = 2, time = 3
     • Skip neighbor 1 (parent).
     • Visit neighbor 3.

   • DFS on node 3:

     • disc[3] = 3, low[3] = 3, time = 4
     • Skip neighbor 2 (parent).
     • Visit neighbor 4.

   • DFS on node 4:

     • disc[4] = 4, low[4] = 4, time = 5

     • Skip neighbor 3 (parent).

     • Visit neighbor 2.

     • Node 2 has been visited already, and it's not the parent of node 4. Update low[4] = min(low[4], disc[2]) = min(4, 2) = 2.

   • Backtrack to node 3: low[3] = min(low[3], low[4]) = min(3, 2) = 2.

     • low[4] > disc[3] is not true (2 > 3 is false). So [3, 4] is not a critical connection.

   • Backtrack to node 2: low[2] = min(low[2], low[3]) = min(2, 2) = 2.

     • Visit neighbor 4 again.

     • Node 4 has been visited already, and it's not the parent of node 2. Update low[2] = min(low[2], disc[4]) = min(2, 4) = 2.

     • Backtrack to node 1: low[1] = min(low[1], low[2]) = min(1, 2) = 1.

     • low[2] > disc[1] is true (2 > 1 is true). So [1, 2] is a critical connection. Add [1, 2] to res.

   • Backtrack to node 0: low[0] = min(low[0], low[1]) = min(0, 1) = 0.

     • low[1] > disc[0] is true (1 > 0 is true). So [0, 1] is a critical connection. Add [0, 1] to res.

4. Result:

   • res = [[1, 2], [0, 1]].

The final result is [[1, 2], [0, 1]], meaning removing either of these connections will split the network into separate parts.

Code

import java.util.*;

public class Solution {

  private int time = 0; // Time counter used in DFS

  public List<List<Integer>> criticalConnections(
    int n,
    List<List<Integer>> connections
  ) {
    // Initialize graph, discovery time and low time arrays
    List<Integer>[] graph = new ArrayList[n];
    int[] disc = new int[n],
      low = new int[n];
    Arrays.fill(disc, -1); // Mark all nodes as unvisited
    List<List<Integer>> res = new ArrayList<>();

    // Build the graph
    for (int i = 0; i < n; i++) {
      graph[i] = new ArrayList<>();
    }
    for (List<Integer> conn : connections) {
      graph[conn.get(0)].add(conn.get(1));
      graph[conn.get(1)].add(conn.get(0));
    }

    // Perform DFS from the first node
    dfs(0, -1, disc, low, graph, res);

    return res;
  }

  private void dfs(
    int u,
    int parent,
    int[] disc,
    int[] low,
    List<Integer>[] graph,
    List<List<Integer>> res
  ) {
    disc[u] = low[u] = ++time; // Initialize discovery and low times
    for (int v : graph[u]) {
      if (v == parent) continue; // Skip the parent node
      if (disc[v] == -1) {
        // If v is not visited
        dfs(v, u, disc, low, graph, res);
        low[u] = Math.min(low[u], low[v]);
        if (low[v] > disc[u]) {
          // Check for a critical connection
          res.add(Arrays.asList(u, v));
        }
      } else {
        low[u] = Math.min(low[u], disc[v]); // Update low time of u
      }
    }
  }

  public static void main(String[] args) {
    Solution sol = new Solution();
    // Example 1
    int n1 = 5;
    List<List<Integer>> connections1 = Arrays.asList(
      Arrays.asList(0, 1),
      Arrays.asList(1, 2),
      Arrays.asList(2, 3),
      Arrays.asList(3, 4),
      Arrays.asList(2, 4)
    );
    System.out.println(sol.criticalConnections(n1, connections1)); // [[2, 3], [3, 4]]

    // Example 2
    int n2 = 4;
    List<List<Integer>> connections2 = Arrays.asList(
      Arrays.asList(0, 1),
      Arrays.asList(0, 2),
      Arrays.asList(1, 2),
      Arrays.asList(2, 3)
    );
    System.out.println(sol.criticalConnections(n2, connections2)); // [[2, 3]]

    // Example 3
    int n3 = 6;
    List<List<Integer>> connections3 = Arrays.asList(
      Arrays.asList(0, 1),
      Arrays.asList(1, 2),
      Arrays.asList(2, 0),
      Arrays.asList(1, 3),
      Arrays.asList(3, 4),
      Arrays.asList(4, 5),
      Arrays.asList(5, 3)
    );
    System.out.println(sol.criticalConnections(n3, connections3)); // [[1, 3]]
  }
}

Complexity Analysis

Time Complexity: The algorithm runs in time, where V is the number of vertices (servers) and E is the number of edges (connections). This is because we perform a DFS traversal of the graph, visiting each vertex and edge once.

Space Complexity: The space complexity is due to the storage required for the graph representation and the recursion stack used by the DFS algorithm.