City Signal Span

Array Easy 22 views

Like1

The emergency office is designing a broadcast plan. Every intersection is labeled 0 to n-1, and you have a list of two-way roads between them. When a transmitter activates at one point, the signal spreads through every connected road. Your goal in City Signal Span is to count exactly how many unique intersections hear the message starting from a specific point.

The "secret sauce" here is Graph Connectivity (BFS/DFS). Treat the city as a graph where roads are edges. Starting from the start intersection, explore every possible path. Isolated intersections or separate road groups stay silent. Duplicate road entries reinforce connections but don't change the total, and the starting point always counts as one recipient. This approach provides a precise integer count the planners can rely on for their drill. It’s a cornerstone skill for anyone building navigation or communication software where network reach is everything!

When the task involves connectivity or route cost, build adjacency carefully and guard against revisiting stale states. Use a visited or best-distance structure to avoid repeated work, and ensure unreachable scenarios return the required fallback value instead of partial traversal results.

Examples

Example 1

Input

n = 4, roads = [[0,1],[1,2],[2,3]], start = 0

Output

Explanation

The signal travels along every road and covers all four intersections.

Example 2

Input

n = 6, roads = [[0,1],[1,2],[2,0],[3,4]], start = 5

Output

Explanation

Intersection 5 is isolated, so only the starting point receives the broadcast.

Example 3

Input

n = 5, roads = [[0,1],[1,2],[3,4]], start = 1

Output

Explanation

Intersections 0, 1, and 2 share a chain of roads, while 3 and 4 are separate.

Algorithm Flow

Recommendation Algorithm Flow for City Signal Span - Budibadu

Best Answers

java

import java.util.*;

class Solution {
    public int city_signal_span(int n, int[][] roads, int start) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] road : roads) {
            adj.get(road[0]).add(road[1]);
            adj.get(road[1]).add(road[0]);
        }
        Set<Integer> visited = new HashSet<>();
        visited.add(start);
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        while (!queue.isEmpty()) {
            int curr = queue.poll();
            for (int neighbor : adj.get(curr)) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    queue.add(neighbor);
                }
            }
        }
        return visited.size();
    }
}

javascript

function city_signal_span(n, roads, start) {
    const adj = Array.from({length: n}, () => []);
    for (const [u, v] of roads) {
        adj[u].push(v);
        adj[v].push(u);
    }
    const visited = new Set([start]);
    const queue = [start];
    while (queue.length > 0) {
        const curr = queue.shift();
        for (const neighbor of adj[curr]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return visited.size;
}

php

<?php
function city_signal_span($n, $roads, $start) {
    $adj = array_fill(0, $n, []);
    foreach ($roads as $road) {
        $adj[$road[0]][] = $road[1];
        $adj[$road[1]][] = $road[0];
    }
    $visited = [$start => true];
    $queue = [$start];
    while (!empty($queue)) {
        $curr = array_shift($queue);
        foreach ($adj[$curr] as $neighbor) {
            if (!isset($visited[$neighbor])) {
                $visited[$neighbor] = true;
                $queue[] = $neighbor;
            }
        }
    }
    return count($visited);
}
?>

python

from typing import List
from collections import deque

def city_signal_span(n: int, roads: List[List[int]], start: int) -> int:
    adj = [[] for _ in range(n)]
    for u, v in roads:
        adj[u].append(v)
        adj[v].append(u)
    visited = {start}
    queue = deque([start])
    while queue:
        curr = queue.popleft()
        for neighbor in adj[curr]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)
    return len(visited)

rust

use std::collections::{HashSet, VecDeque};

pub fn city_signal_span(n: i32, roads: Vec<Vec<i32>>, start: i32) -> i32 {
    let mut adj = vec![vec![]; n as usize];
    for road in roads {
        let u = road[0] as usize;
        let v = road[1] as usize;
        adj[u].push(v);
        adj[v].push(u);
    }
    let mut visited = HashSet::new();
    visited.insert(start as usize);
    let mut queue = VecDeque::new();
    queue.push_back(start as usize);
    while let Some(curr) = queue.pop_front() {
        for &neighbor in &adj[curr] {
            if !visited.contains(&neighbor) {
                visited.insert(neighbor);
                queue.push_back(neighbor);
            }
        }
    }
    visited.len() as i32
}

typescript

function city_signal_span(n: number, roads: number[][], start: number): number {
    const adj: number[][] = Array.from({length: n}, () => []);
    for (const [u, v] of roads) {
        adj[u].push(v);
        adj[v].push(u);
    }
    const visited = new Set([start]);
    const queue = [start];
    while (queue.length > 0) {
        const curr = queue.shift()!;
        for (const neighbor of adj[curr]) {
            if (!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return visited.size;
}

Comments (0)

Join the Discussion

Share your thoughts, ask questions, or help others with this problem.

City Signal Span

Examples

Algorithm Flow

Best Answers

Solutions Coming Soon

Related Array Problems

Longest Consecutive Sequence

Garden Relay Count

Lantern Stall Picks

Festival Stall Order

Studio Lighting Slots

Seaport Ferry Gate Control

Comments (0)

Join the Discussion