1192. Critical Connections in a Network

HardDepth-First SearchGraphBiconnected Component

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.

Flowchart Walkthrough

First, let's pin down the algorithm using the Flowchart. Here's a step-by-step walkthrough:

Is it a graph?

Yes: The network is represented as a graph where servers are nodes and connections are edges.

Is it a tree?

No: Although it might not have cycles, the problem explicitly involves finding critical connections which implies potentially multiple paths thereby not strictly forming a tree structure.

Is the problem related to directed acyclic graphs (DAGs)?

No: The problem is about finding specific edges in an undirected graph, rather than processing or sorting nodes in a directed graph.

Is the problem related to shortest paths?

No: The focus is on identifying vulnerable connections, not on calculating paths between nodes.

Does the problem involve connectivity?

Yes: The task is to determine connections that, if removed, would increase the number of connected components, or disconnect parts of the network.

Is the graph weighted?

No: The description only talks about connections without assigning any cost or weight to them.

Conclusion: The flowchart suggests using DFS for this unweighted connectivity problem since it helps in exploring each connection deeply to check its criticality. Depth-First Search is suitable for exploring all the nodes deeply connected to a particular node, which is useful in identifying critical connections in a network.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

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.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

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:

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

Represented visually, the network might look like this:

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.

Create an adjacency list g for the graph:

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

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

dfn = [0, 0, 0, 0, 0]
low = [0, 0, 0, 0, 0]

Initialize the global counter now to 0.
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.
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

1from typing import List
2
3class Solution:
4    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
5        # Initialize the 'discovery time' and 'low time' arrays to keep track of the earliest visited vertex (ancestor) that can be reached from a vertex.
6        discovery_time = [0] * n
7        low_time = [0] * n
8      
9        # The current time count used for both discovery_time and low_time values.
10        current_time = 0
11      
12        # This array will hold the result: a list of critical connections.
13        critical_connections = []
14      
15        # Utility function to perform the Tarjan's DFS algorithm.
16        # `vertex` : the current vertex being explored.
17        # `parent` : the predecessor vertex of the current vertex in the DFS tree.
18        def tarjan_dfs(vertex: int, parent: int):
19            # We have access to the outer scope's "current_time" variable.
20            nonlocal current_time
21          
22            # Increment the current discovery time.
23            current_time += 1
24          
25            # Initialize the discovery time and low value for the current vertex.
26            discovery_time[vertex] = low_time[vertex] = current_time
27          
28            # Iterate through all the connected vertices of the current vertex.
29            for neighbor in graph[vertex]:
30                # Skip the exploration of the edge leading back to the parent vertex.
31                if neighbor == parent:
32                    continue
33              
34                if not discovery_time[neighbor]:
35                    # The neighbor has not been visited, so we run tarjan_dfs on it.
36                    tarjan_dfs(neighbor, vertex)
37                  
38                    # Update the low_time for the current vertex with the value from the neighbor if it's smaller.
39                    low_time[vertex] = min(low_time[vertex], low_time[neighbor])
40                  
41                    # If the low time value of the neighbor is greater than the discovery time of the current vertex,
42                    # it means that no back edge exists and hence, it is a critical connection.
43                    if low_time[neighbor] > discovery_time[vertex]:
44                        critical_connections.append([vertex, neighbor])
45              
46                else:
47                    # If the neighbor was already visited, update the low_time of the current vertex.
48                    low_time[vertex] = min(low_time[vertex], discovery_time[neighbor])
49
50        # Construct the graph as an adjacency list from the list of connections.
51        graph = [[] for _ in range(n)]
52        for a, b in connections:
53            graph[a].append(b)
54            graph[b].append(a)
55
56        # Perform Tarjan's algorithm starting from the first vertex.
57        tarjan_dfs(0, -1)
58      
59        return critical_connections
60
61# Example usage:
62# solution = Solution()
63# critical_edges = solution.criticalConnections(n=5, connections=[[0, 1], [1, 2], [2, 0], [1, 3], [3, 4]])
64# print(critical_edges)  # Output would be the list of critical connections: [[1, 3], [3, 4]]
65

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5class Solution {
6    private int currentTime;
7    private List<Integer>[] graph;
8    private List<List<Integer>> criticalConnectionsList = new ArrayList<>();
9    private int[] discoveryTime;
10    private int[] lowTime;
11
12    // The function to find all critical connections in a network
13    public List<List<Integer>> criticalConnections(int n, List<List<Integer>> connections) {
14        initializeGraph(n, connections);
15
16        // Apply Tarjan's algorithm starting from node 0, with no parent (-1).
17        tarjanAlgorithm(0, -1);
18
19        return criticalConnectionsList;
20    }
21
22    private void initializeGraph(int numberOfNodes, List<List<Integer>> connections) {
23        // Initialize the graph as an adjacency list
24        graph = new List[numberOfNodes];
25        Arrays.setAll(graph, k -> new ArrayList<>());
26        // Initialize discovery times and low times
27        discoveryTime = new int[numberOfNodes];
28        lowTime = new int[numberOfNodes];
29        // Build graph from the connections list
30        for (List<Integer> edge : connections) {
31            int node1 = edge.get(0);
32            int node2 = edge.get(1);
33            graph[node1].add(node2);
34            graph[node2].add(node1);
35        }
36    }
37
38    // Tarjan's algorithm to find critical connections (bridges) in the graph
39    private void tarjanAlgorithm(int node, int parent) {
40        discoveryTime[node] = lowTime[node] = ++currentTime;
41
42        for (int neighbor : graph[node]) {
43            // If the neighbor is the parent, skip it
44            if (neighbor == parent) {
45                continue;
46            }
47
48            // If the neighbor hasn't been visited yet
49            if (discoveryTime[neighbor] == 0) {
50                // Recursively apply Tarjan's algorithm to the neighbor
51                tarjanAlgorithm(neighbor, node);
52
53                // Update the low time
54                lowTime[node] = Math.min(lowTime[node], lowTime[neighbor]);
55
56                // If the low time of the neighbor is greater than the discovery time of current node,
57                // it means that the edge node-neighbor is a critical connection
58                if (lowTime[neighbor] > discoveryTime[node]) {
59                    criticalConnectionsList.add(Arrays.asList(node, neighbor));
60                }
61            } else {
62                // If the neighbor has been visited, update the low time of current node
63                lowTime[node] = Math.min(lowTime[node], discoveryTime[neighbor]);
64            }
65        }
66    }
67}
68

1#include <vector>
2#include <functional>
3using namespace std;
4
5class Solution {
6public:
7    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
8        int currentTime = 0; // Used to assign discovery times
9        vector<int> discoveryTime(n, 0); // Stores discovery times of nodes
10        vector<int> lowTime(n, 0); // Stores the lowest discovery time reachable from the node
11        vector<int> graph[n]; // Adjacency list to represent graph
12
13        // Construct the graph
14        for (auto& connection : connections) {
15            int nodeA = connection[0], nodeB = connection[1];
16            graph[nodeA].push_back(nodeB);
17            graph[nodeB].push_back(nodeA);
18        }
19
20        vector<vector<int>> criticalEdges; // Store the critical edges
21
22        // Lambda function to perform Tarjan's algorithm recursively
23        function<void(int, int)> tarjan = [&](int node, int parent) -> void {
24            discoveryTime[node] = lowTime[node] = ++currentTime; // Initialize discovery and low times
25            for (int neighbor : graph[node]) {
26                if (neighbor == parent) { // If neighbor is parent, skip to next neighbor
27                    continue;
28                }
29                if (discoveryTime[neighbor] == 0) { // If neighbor hasn't been visited
30                    tarjan(neighbor, node); // Recurse on the neighbor
31                    lowTime[node] = min(lowTime[node], lowTime[neighbor]); // Update low time
32
33                    // Check for critical connections
34                    if (lowTime[neighbor] > discoveryTime[node]) {
35                        criticalEdges.push_back({node, neighbor});
36                    }
37                } else {
38                    // If the neighbor has been visited, update the low time of the current node
39                    lowTime[node] = min(lowTime[node], discoveryTime[neighbor]);
40                }
41            }
42        };
43
44        // Start Tarjan's algorithm from the first node with no parent
45        tarjan(0, -1);
46
47        return criticalEdges; // Return the critical connections found in the graph
48    }
49};
50

1function criticalConnections(nodeCount: number, connections: number[][]): number[][] {
2    // Initialize a variable to track the time of node visitation during the DFS. 
3    let visitTime: number = 0;
4
5    // Create the graph initially as an array of empty arrays representing the adjacency list.
6    const graph: number[][] = Array.from({ length: nodeCount }, () => []);
7
8    // Instantiate the discover and low-link arrays to record the sequence of discovery and the oldest reachable ancestor's discovery number.
9    const discoveryTime: number[] = Array(nodeCount).fill(0);
10    const lowLink: number[] = Array(nodeCount).fill(0);
11
12    // Build the graph from the given connections.
13    for (const [node1, node2] of connections) {
14        graph[node1].push(node2);
15        graph[node2].push(node1);
16    }
17
18    // Define an output list to store the critical connections.
19    const criticalEdges: number[][] = [];
20
21    // Define the Tarjan's DFS algorithm.
22    function tarjanDFS(currentNode: number, parentNode: number) {
23        // Set the discover time and low-link value.
24        discoveryTime[currentNode] = lowLink[currentNode] = ++visitTime;
25
26        // Iterate through neighbors of the current node.
27        for (const neighbor of graph[currentNode]) {
28            // Ignore the edge pointing back to the parent node.
29            if (neighbor === parentNode) continue;
30
31            // If neighbor is not visited, continue the DFS.
32            if (!discoveryTime[neighbor]) {
33                tarjanDFS(neighbor, currentNode);
34              
35                // Update the current node's low-link value.
36                lowLink[currentNode] = Math.min(lowLink[currentNode], lowLink[neighbor]);
37
38                // Check if the current edge is a critical connection.
39                if (lowLink[neighbor] > discoveryTime[currentNode]) {
40                    criticalEdges.push([currentNode, neighbor]);
41                }
42            } else {
43                // The neighbor is already visited, update low-link if necessary.
44                lowLink[currentNode] = Math.min(lowLink[currentNode], discoveryTime[neighbor]);
45            }
46        }
47    }
48
49    // Start the DFS from the first node, considering no parent initially.
50    tarjanDFS(0, -1);
51
52    // Return the list of critical connections.
53    return criticalEdges;
54}
55

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.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan: