# Maximal Network Connectivity

##### January 8, 2024

## Problem #

Given a network of `n`

cities and a list of roads connecting these cities, find the maximum number of cities that can be connected directly or indirectly via these roads. You can assume that the roads are bidirectional and that each pair of cities has at most one direct road connecting them.

### Example: #

Input: `n = 4`

, `roads = [[0, 1], [0, 2], [1, 2], [1, 3]]`

Output: `4`

Explanation: All cities can be connected directly or indirectly by the given roads.

## Solution #

The solution can be approached using Union-Find (Disjoint Set Union) algorithm to keep track of connected components in the network. The idea is to iterate through the roads, joining cities into connected components. After processing all roads, we check the size of the largest connected component.

### Algorithm Steps #

- Initialize an array
`parent`

to keep track of the parent of each city in the disjoint set. - Define a function
`find`

to find the root parent of a city. - Define a function
`union`

to join two cities into one connected component. - Iterate through the
`roads`

list, applying`union`

for each pair of connected cities. - Use a hash map or array to count the number of cities in each connected component.
- Find the maximum size among all connected components.

### Code in Python: #

```
def maximalNetwork(n, roads):
parent = [i for i in range(n)]
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]
def union(x, y):
px = find(x)
py = find(y)
if px != py:
parent[px] = py
for u, v in roads:
union(u, v)
component_size = [0] * n
for i in range(n):
component_size[find(i)] += 1
return max(component_size)
# Example Usage
print(maximalNetwork(4, [[0, 1], [0, 2], [1, 2], [1, 3]])) # Output: 4
```

### Time Complexity: #

O(N + R), where `N`

is the number of cities and `R`

is the number of roads. The Union-Find operations (`find`

and `union`

) take almost constant time (amortized O(1)) due to path compression.

### Space Complexity: #

O(N), for the `parent`

array and the `component_size`

array.

This problem illustrates an application of Union-Find data structure in network analysis, efficiently solving a connectivity problem that’s common in graph theory and network science.