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 #

1. Initialize an array parent to keep track of the parent of each city in the disjoint set.
2. Define a function find to find the root parent of a city.
3. Define a function union to join two cities into one connected component.
4. Iterate through the roads list, applying union for each pair of connected cities.
5. Use a hash map or array to count the number of cities in each connected component.
6. 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.