• 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 O(V + E), 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