Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Solution: Critical Connections in a Network
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

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]]
Image
  • 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]]
Image
  • 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]]
Image
  • Justification: Removing [1, 3] will disconnect servers 3, 4, and 5 from the rest of the network.

Constraints:

  • 2 <= n <= 10<sup>5</sup>
  • n - 1 <= connections.length <= 10<sup>5</sup>
  • 0 <= a<sub>i</sub>, b<sub>i</sub> <= n - 1
  • a<sub>i</sub> != b<sub>i</sub>
  • 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

Python3
Python3

. . . .

Complexity Analysis

Time Complexity: The algorithm runs in O(V + E) 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 O(V + E) due to the storage required for the graph representation and the recursion stack used by the DFS algorithm.

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible