# 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: #

- Initialize arrays to store discovery times and low values for each vertex.
- Initialize a parent array to keep track of the DFS tree.
- Perform DFS on each unvisited vertex.
- During DFS, update the discovery time and low values.
- If a vertex
`u`

is an articulation point, consider it as a potential answer. - 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.