How Many Broadcast Servers Are Needed? BFS & DFS Solutions Explained

Problem Statement

Servers can be directly or indirectly connected. The N×N matrix entry matrix[i][j]=1 indicates a direct link between server i and j, while 0 means no direct link. A broadcast can be sent over either direct or indirect connections. Determine the minimum number of servers that must start a broadcast so that every server eventually receives the message.

Input

The first line contains N (1 ≤ N ≤ 40). The following N lines each contain N integers (0 or 1) separated by spaces, forming the adjacency matrix.

Output

A single integer representing the required number of broadcasting servers.

Examples

Example 1

1 0 0
0 1 0
0 0 1

Output: 3

Example 2

1 1
1 1

Output: 1

Solution Idea

The problem is identical to counting the number of connected components in an undirected graph, the same as LeetCode 547. Each component requires one initial broadcast. Perform either BFS or DFS from every unvisited node, marking visited nodes, and increment a counter for each new component.

Reference Implementations (Python)

BFS Version

from collections import deque

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

ans = 0
checkList = [0] * n

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

print(ans)

DFS Version

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

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

ans = 0
checkList = [0] * n

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

print(ans)

Complexity Analysis

Time complexity: O(N²) because the entire adjacency matrix is scanned. Space complexity: O(N) for the visited array and the queue/recursion stack.