{x}
blog image

Critical Connections in a Network

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network 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 server.

Return all critical connections in the network in any order.

 

Example 1:

Input: n = 4, connections = [[0,1],[1,2],[2,0],[1,3]]
Output: [[1,3]]
Explanation: [[3,1]] is also accepted.

Example 2:

Input: n = 2, connections = [[0,1]]
Output: [[0,1]]

 

Constraints:

  • 2 <= n <= 105
  • n - 1 <= connections.length <= 105
  • 0 <= ai, bi <= n - 1
  • ai != bi
  • There are no repeated connections.

1192. Critical Connections in a Network

This problem asks to find all the critical connections in a network represented by a graph. A critical connection is an edge whose removal disconnects the graph. This is equivalent to finding bridges in an undirected graph. The Tarjan's algorithm is an efficient way to solve this.

Tarjan's Algorithm

Tarjan's algorithm uses Depth-First Search (DFS) to find bridges and articulation points in a graph. It assigns two values to each node:

  • dfn[u] (Discovery Time): The order in which the node u is visited during the DFS.
  • low[u] (Lowest Reachable Ancestor): The lowest discovery time reachable from node u through either a tree edge (edge in the DFS tree) or a back edge (edge connecting a node to an ancestor in the DFS tree).

Finding Bridges: An edge (u, v) is a bridge if low[v] > dfn[u] (or equivalently low[u] > dfn[v]). This means that there's no back edge from the subtree rooted at v to any ancestor of u, so removing the edge (u, v) would disconnect the graph.

Time Complexity Analysis

The algorithm performs a single DFS traversal of the graph. The DFS visits each node and edge exactly once. Therefore, the time complexity is O(V + E), where V is the number of vertices (servers) and E is the number of edges (connections). In this problem, V = n and E is the number of connections.

Space Complexity Analysis

The space complexity is dominated by the recursion stack during the DFS, which in the worst case could be O(V) for a very deep tree. Additionally, we use arrays dfn and low of size V, and adjacency list g which takes up to O(V+E) space in the worst case. So the overall space complexity is O(V + E).

Code Explanation (Python)

class Solution:
    def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
        graph = [[] for _ in range(n)]
        for u, v in connections:
            graph[u].append(v)
            graph[v].append(u)
 
        dfn = [-1] * n  # Initialize discovery time to -1
        low = [-1] * n  # Initialize lowest reachable ancestor to -1
        bridges = []
        time = 0
 
        def dfs(u: int, parent: int):
            nonlocal time
            dfn[u] = low[u] = time
            time += 1
 
            for v in graph[u]:
                if v == parent:
                    continue  # Skip the parent node
                if dfn[v] == -1:  # If v is not visited
                    dfs(v, u)
                    low[u] = min(low[u], low[v])
                    if low[v] > dfn[u]:  # Bridge condition
                        bridges.append([u, v])
                else:  # If v is visited (back edge)
                    low[u] = min(low[u], dfn[v])
 
        dfs(0, -1)  # Start DFS from node 0
        return bridges

The Python code first builds the adjacency list representation of the graph. Then, it performs the DFS using the dfs function. The dfn and low arrays are updated during the DFS, and bridges are identified based on the bridge condition. The resulting bridges list contains all the critical connections. Other language implementations follow a similar structure and logic, differing only in syntax.