1192. Critical Connections in a Network

Problem Description

The task is to find all the critical connections in a network of servers. A server network is represented as an undirected graph where nodes represent servers and edges represent connections between them. The servers are numbered from 0 to n - 1. A critical connection is defined as an edge that, if removed, will prevent some servers from reaching others. These are essentially the connections that are not part of any cycle. The goal is to return a list of these critical connections.

Intuition

To identify critical connections, we need to find edges that are not part of any cycles in the graph. To do this, we can use Tarjan's algorithm which is designed to identify strongly connected components in a graph. A strongly connected component (SCC) is a part of the graph where every vertex is reachable from every other vertex in the same component.

Tarjan's algorithm uses Depth-First Search (DFS) and maintains two arrays, dfn and low, which help to track the discovery time of a node and the lowest discovery time reachable from that node, without using the parent-child connection, respectively.

The idea is to perform a DFS from each unvisited node and use the dfn and low arrays to detect whether an edge is a bridge (or critical connection). A bridge is encountered if the low value of the child node is greater than the discovery time (dfn) of the parent, which means that there is no back edge from the child or any of its descendants to the parent or any of its ancestors.

Learn more about Depth-First Search, Graph and Biconnected Component patterns.

Solution Approach

The solution uses the Tarjan's algorithm for finding the strongly connected components (SCCs) and more specifically, finding bridges or critical connections in an undirected graph. Let's walk through the steps and the key components of the implementation:

• First, we create an adjacency list, g, to represent the graph. This allows us to store the graph in such a way that for every server a, we can efficiently access all the servers b to which it's connected, by simply iterating over g[a].

• Two arrays, dfn and low, with lengths equal to the number of servers (n), are initialized to track the discovery time of nodes, and the lowest discovery time reachable from each node, respectively.

• A helper function tarjan is implemented to perform DFS starting from a node, marking the discovery time, updating low values, and identifying bridges. The parameters for this function are a (current node) and fa (father node or the node from which we arrived at the current node).

• We keep a global counter now to assign discovery times to the nodes. Discovery time is simply an incrementing counter value assigned to a node when it's first visited.

• For each node that has not been visited (i.e., not assigned a discovery time in dfn), we perform a tarjan DFS traversal.

  • Within the tarjan function, each child b of the current node a (excluding the father fa) is visited.
    • If the child has not been visited (dfn[b] == 0), a recursive call to tarjan is made for the child, treating the current node as its parent.
      • After the recursive call, if the low[b] is greater than the dfn[a] of the current node, the edge from a to b is identified as a bridge and added to the answer list ans.
      • The low[a] value is updated to the minimum of its current value and the low[b] value returned from the DFS call. This step essentially checks if there is a back edge from the descendants of b that connects to ancestors of a at a lower discovery time.
    • If the child has already been visited (dfn[b] != 0), we update low[a] to the minimum of its current value and dfn[b], indicating that there is a cycle and a-b is not a bridge.

• The algorithm starts by calling tarjan(0, -1) from the first server assuming the graph is connected (if the graph is not guaranteed to be connected, this would be wrapped in a loop to start tarjan from every unvisited node).

• Finally, the collected bridges in the ans list are returned, which gives us all critical connections.

This solution effectively detects all the critical connections in a network by leveraging the depth-first search and leveraging Tarjan's algorithm to find bridges in an undirected graph.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach described above. Suppose we have the following undirected graph represented by the server network where nodes represent servers and edges represent connections between them:

1Servers: 0, 1, 2, 3, 4
2Connections: (0-1), (1-2), (2-0), (1-3), (3-4)

Represented visually, the network might look like this:

1    0
2   / \
3  1---2
4  | 
5  3
6  |
7  4

In this graph, servers 0, 1, and 2 form a cycle, while the connections (1-3) and (3-4) do not participate in any cycle and therefore are critical connections.

We will use the steps of the solution approach to identify these critical connections.

1. Create an adjacency list g for the graph:

   1g = {
   2    0: [1, 2],
   3    1: [0, 2, 3],
   4    2: [0, 1],
   5    3: [1, 4],
   6    4: [3]
   7}

2. Initialize dfn and low arrays of size n=5 (since we have 5 servers):

   1dfn = [0, 0, 0, 0, 0]
   2low = [0, 0, 0, 0, 0]

3. Initialize the global counter now to 0.

4. Perform a DFS starting with the server 0 and its father as -1 (no father since it's the starting node):

   1. For node 0, we set dfn[0] = low[0] = now = 1.
      • Recurse on its unvisited child, 1:
        • Set dfn[1] = low[1] = now = 2.
        • Recurse on its unvisited child, 2:
          • Set dfn[2] = low[2] = now = 3.
          • Both children 0 and 1 of 2 have been visited, but since 0 is the parent node, we only update low[2] to the minimum of low[2] and dfn[0], which is 1.
        • Back to 1, since low[2] (1) is not greater than dfn[1] (2), the connection (1-2) is not a bridge.
        • Update low[1] to the minimum of low[1] and low[2], which remains 2.
        • Next, recurse on child 3:
          • Set dfn[3] = low[3] = now = 4.
          • Child 4 of 3 is unvisited:
            • Set dfn[4] = low[4] = now = 5.
            • Child 3 is visited and is the parent, so we do not update low[4].
          • Since low[4] (5) is greater than dfn[3] (4), we identify (3-4) as a bridge and add it to ans.
          • After recursing, update low[3] to the minimum of low[3] and low[4], but it remains 4.
          • Since low[3] (4) is greater than dfn[1] (2), we identify (1-3) as a bridge and add it to ans.

5. After the DFS is complete, we have the global variable ans containing our critical connections, which in this case will be [(1-3), (3-4)].

This example demonstrates the use of Tarjan's algorithm to identify all the critical connections in the network, leveraging DFS and the concept of low and discovery times to find bridges in an undirected graph.

Solution Implementation

Time and Space Complexity

The given code is an implementation of Tarjan's algorithm to find critical connections (or bridges) in a graph.

• The time complexity of this algorithm is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because every vertex and every edge is visited exactly once during the depth-first search (DFS). The work done at each vertex is proportional to its degree (the number of connections it has), which all added together gives us the number of edges. Therefore, the time complexity encompasses visiting all vertices and edges once.

• The space complexity of the code is O(V + E) as well. This is due to several factors:

  • The adjacency list g which can hold up to 2E elements since it's an undirected graph and each edge appears twice.
  • The dfn and low arrays, each of which has a length of V.
  • The recursion stack for DFS, which, in the worst case, could hold all V vertices if the graph is a single long path.
  • In some cases, there is also a system stack used during the recursion which can grow up to O(V) in space.

Therefore, considering both vertices and edges for the memory occupied by the adjacency list and the recursion stack, the combined space complexity is O(V + E).

Learn more about how to find time and space complexity quickly using problem constraints.