Maximal Network Connectivity II

January 14, 2024

Problem #

Given a network represented as a graph with n nodes labeled from 0 to n-1 and an array connections where connections[i] = [a, b] indicates that there is a bidirectional road between nodes a and b, your task is to find the node that, if removed, would minimize the connectivity of the network. The connectivity of a network is defined as the number of nodes that are reachable from any node. Return the label of such a node. If there are multiple nodes satisfying this condition, return the smallest label.

Example: #

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

Solution Approach: #

The problem can be solved using graph theory concepts, particularly by identifying articulation points (or cut vertices) in the graph. An articulation point is a vertex that, when removed, increases the number of connected components in the graph. The algorithm involves performing a Depth-First Search (DFS) traversal and keeping track of discovery times of vertices and the earliest visited vertex that can be reached from the subtree rooted with the current vertex.

Algorithm Steps: #

1. Initialize arrays to store discovery times and low values for each vertex.
2. Initialize a parent array to keep track of the DFS tree.
3. Perform DFS on each unvisited vertex.
4. During DFS, update the discovery time and low values.
5. If a vertex u is an articulation point, consider it as a potential answer.
6. After DFS, choose the vertex with the smallest label among all articulation points.

Code: #

def findArticulationPoints(n, connections):
    def dfs(u, discovery, low, parent, time):
        children = 0
        discovery[u] = low[u] = time[0]
        time[0] += 1

        for v in graph[u]:
            if discovery[v] == -1:
                parent[v] = u
                children += 1
                dfs(v, discovery, low, parent, time)

                low[u] = min(low[u], low[v])

                if parent[u] == -1 and children > 1:
                    articulation_points.add(u)
                if parent[u] != -1 and low[v] >= discovery[u]:
                    articulation_points.add(u)
            elif v != parent[u]:
                low[u] = min(low[u], discovery[v])

    graph = [[] for _ in range(n)]
    for a, b in connections:
        graph[a].append(b)
        graph[b].append(a)

    discovery = [-1] * n
    low = [-1] * n
    parent = [-1] * n
    time = [0]
    articulation_points = set()

    for i in range(n):
        if discovery[i] == -1:
            dfs(i, discovery, low, parent, time)

    return min(articulation_points) if articulation_points else -1

# Example usage
print(findArticulationPoints(5, [[0, 1], [1, 2], [2, 3], [3, 4]]))  # Output: 2

Time Complexity: #

The time complexity is O(V + E), where V is the number of vertices and E is the number of edges in the graph. This is because the algorithm performs a DFS traversal of the graph.

Space Complexity: #

The space complexity is O(V), due to the storage of graph data, discovery times, low values, and parent information for each vertex.