We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Critical Connections in a Network

Difficulty: Hard

Problem Description

There are n servers numbered from 0 to n - 1 connected by undirected server-to-server connections forming a network where connections[i] = [a_i, b_i] represents a connection between servers a_i and b_i. 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.

Key Insights

  • A critical connection can be identified using Depth-First Search (DFS).
  • The problem can be visualized as finding bridges in a graph.
  • The discovery and low-link values during DFS traversal help in identifying critical connections.
  • Each connection is considered critical if there is no back edge connecting its endpoints to one of the endpoints' ancestors in the DFS tree.

Space and Time Complexity

Time Complexity: O(V + E), where V is the number of vertices (servers) and E is the number of edges (connections). Space Complexity: O(V + E) for storing the graph and the visited nodes.

Solution

The solution uses a Depth-First Search (DFS) approach to explore the graph formed by the servers and their connections. We maintain an array to keep track of the discovery time of each server and another array to store the lowest discovery time reachable from that server. By comparing these values during DFS, we can determine if a connection is critical (i.e., if removing it would increase the number of connected components in the graph).

Code Solutions

def criticalConnections(n, connections):
    from collections import defaultdict

    # Create a graph from the connections
    graph = defaultdict(list)
    for a, b in connections:
        graph[a].append(b)
        graph[b].append(a)

    # Initialize discovery and low arrays
    discovery = [-1] * n
    low = [-1] * n
    result = []
    time = [0]  # Using a list to maintain state in nested function

    def dfs(node, parent):
        discovery[node] = low[node] = time[0]
        time[0] += 1

        for neighbor in graph[node]:
            if neighbor == parent:
                continue
            if discovery[neighbor] == -1:  # If neighbor is not visited
                dfs(neighbor, node)
                low[node] = min(low[node], low[neighbor])
                # Check if the edge is a critical connection
                if low[neighbor] > discovery[node]:
                    result.append([node, neighbor])
            else:  # If the neighbor is visited
                low[node] = min(low[node], discovery[neighbor])

    # Start DFS for each node
    for i in range(n):
        if discovery[i] == -1:
            dfs(i, -1)

    return result
← Back to All Questions