Compute the Longest Broadcast Response Time with BFS

Problem Description

In a communication network there are N nodes labeled from 1 to N. Every pair of directly connected nodes incurs a time delay of one unit. When a chosen node broadcasts a message, every node that receives it immediately sends a response back along the same path. The task is to compute the smallest number of time units the broadcasting node must wait to receive all responses.

Input

5 7
1 4
2 1
2 3
2 4
3 4
3 5
4 5
2

Output

4

Explanation

From node 2 to node 5 the shortest delay is 2 units, while all other nodes are at distance 1. The longest round‑trip distance is therefore 2 × 2 = 4 time units, which is the required answer.

Solution Idea

This problem reduces to finding the maximum BFS level from the start node in an undirected graph; the answer is (level‑1) × 2 .

Implementation (Python)

from collections import deque, defaultdict

# Read number of nodes N and number of edges T
N, T = map(int, input().split())

# Build adjacency list for an undirected graph
table = defaultdict(list)
for _ in range(T):
    x, y = map(int, input().split())
    table[x].append(y)
    table[y].append(x)

# Starting node for the broadcast
start = int(input())

# BFS preparation
checkList = [0] * (N + 1)
checkList[start] = 1
q = deque([start])
level = 0

while q:
    level += 1
    qSize = len(q)
    for _ in range(qSize):
        cur = q.popleft()
        for nxt in table[cur]:
            if checkList[nxt] == 0:
                checkList[nxt] = 1
                q.append(nxt)

# The longest distance is (level‑1); round‑trip time is double that
print((level - 1) * 2)

Complexity Analysis

Time complexity: O(N) – each node is visited once.

Space complexity: O(N^2) – the adjacency list may occupy up to N^2 entries in the worst case.