Find the Largest Connected Linux Distribution Group with BFS/DFS

Problem Description

Linux distributions can be related to each other (e.g., Ubuntu is based on Debian, Mint on Ubuntu). A set of related distributions forms a connected component. Given an n × n adjacency matrix isConnected where isConnected[i][j] = 1 indicates a direct relation between distribution i and j, the task is to return the size of the largest connected component.

Input / Output

The first line contains the integer N (1 ≤ N ≤ 200), the total number of distributions. The following N lines each contain N integers (0 or 1) describing the adjacency matrix. The output is a single integer: the maximum number of distributions in any connected component.

Example

4
1 1 0 0
1 1 1 0
0 1 1 0
0 0 0 1

The first three distributions are connected (size 3) and the fourth is isolated (size 1), so the answer is 3.

Solution Idea

The problem is equivalent to finding the largest connected component in an undirected graph represented by an adjacency matrix, similar to LeetCode 547 (Number of Provinces) and LeetCode 695 (Max Area of Island). Either BFS or DFS can be used to explore each component and track its size.

Algorithm (BFS)

# BFS
from collections import deque

n = int(input())
isConnected = []
for _ in range(n):
    isConnected.append(list(map(int, input().split())))

ans = 0
checkList = [0] * n  # visited flag for each distribution

for i in range(n):
    if checkList[i] == 0:
        q = deque([i])
        checkList[i] = 1
        cur_num = 0
        while q:
            x = q.popleft()
            cur_num += 1
            for y in range(n):
                if x != y and checkList[y] == 0 and isConnected[x][y] == 1:
                    q.append(y)
                    checkList[y] = 1
        ans = max(ans, cur_num)

print(ans)

Algorithm (DFS)

# DFS
import sys
sys.setrecursionlimit(10000)

def dfs(x, isConnected, checkList):
    global cur_num
    cur_num += 1
    checkList[x] = 1
    for y in range(n):
        if y != x and checkList[y] == 0 and isConnected[x][y] == 1:
            dfs(y, isConnected, checkList)

n = int(input())
isConnected = []
for _ in range(n):
    isConnected.append(list(map(int, input().split())))

ans = 0
checkList = [0] * n

for i in range(n):
    if checkList[i] == 0:
        cur_num = 0
        dfs(i, isConnected, checkList)
        ans = max(ans, cur_num)

print(ans)

Complexity Analysis

Time complexity: O(N²), because the entire adjacency matrix is scanned during the BFS/DFS traversals.

Space complexity: O(N) for the visited array and the queue/recursion stack.