Riverside Power Grid Check

Array Easy 2 views

Like14

The riverside utility district monitors electrical substations (0 to n-1) linked by bidirectional power lines. When crews start a safety check from an Origin, they follow the lines to inspect every reachable neighbor. Your goal in Riverside Power Grid Check is to find the total count of unique substations verified during a single tour starting from that home base.

The "secret sauce" here is Network Exploration (Traversal). Use BFS or DFS to branch out from the origin substation and mark each new node you hit. Disconnected sections of the grid remain unchecked and are excluded from your tally. Duplicate lines or self-loops in the engineering map shouldn't change the final result—you only count each unique substation once. Return the total coverage as a single integer. This helps the district ensure all reachable infrastructure is safe while identifying exactly which pockets of the grid are currently isolated from the main supply line!

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 = 6, lines = [[0,1],[1,2],[0,2],[3,4]], origin = 3

Output

Explanation

Only substations 3 and 4 are reachable from the origin segment.

Example 2

Input

n = 5, lines = [[0,1],[1,2],[2,3],[3,4]], origin = 0

Output

Explanation

The crew moves sequentially across each line and inspects every substation.

Example 3

Input

n = 4, lines = [], origin = 2

Output

Explanation

With no power lines connected, only the origin substation is inspected.

Algorithm Flow

Recommendation Algorithm Flow for Riverside Power Grid Check - Budibadu

Best Answers

java

import java.util.*;
class Solution {
    public int power_grid_coverage(int n, int[][] lines, int origin) {
        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] line : lines) {
            adj.computeIfAbsent(line[0], k -> new ArrayList<>()).add(line[1]);
            adj.computeIfAbsent(line[1], k -> new ArrayList<>()).add(line[0]);
        }

        if (!adj.containsKey(origin)) return 1;

        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        visited.add(origin);
        queue.offer(origin);
        
        while (!queue.isEmpty()) {
            int u = queue.poll();
            if(adj.containsKey(u)) {
                for (int v : adj.get(u)) {
                    if (visited.add(v)) {
                        queue.offer(v);
                    }
                }
            }
        }
        
        return visited.size();
    }
}

javascript

function power_grid_coverage(n, lines, origin) {
    const adj = new Map();
    for (const [u, v] of lines) {
        if (!adj.has(u)) adj.set(u, []);
        adj.get(u).push(v);
        if (!adj.has(v)) adj.set(v, []);
        adj.get(v).push(u);
    }

    if (!adj.has(origin)) return 1;

    const visited = new Set();
    visited.add(origin);
    const queue = [origin];

    while (queue.length > 0) {
        const u = queue.shift();
        const neighbors = adj.get(u);
        if (neighbors) {
            for (const v of neighbors) {
                if (!visited.has(v)) {
                    visited.add(v);
                    queue.push(v);
                }
            }
        }
    }
    return visited.size;
}

php

<?php
function power_grid_coverage($n, $lines, $origin) {
    $adj = [];
    foreach ($lines as $line) {
        $adj[$line[0]][] = $line[1];
        $adj[$line[1]][] = $line[0];
    }

    if (!isset($adj[$origin])) {
        return 1;
    }

    $visited = [$origin => true];
    $queue = [$origin];
    $head = 0;

    while ($head < count($queue)) {
        $u = $queue[$head++];
        if (isset($adj[$u])) {
            foreach ($adj[$u] as $v) {
                if (!isset($visited[$v])) {
                    $visited[$v] = true;
                    $queue[] = $v;
                }
            }
        }
    }

    return count($visited);
}
?>

python

import collections
from typing import List

def power_grid_coverage(n: int, lines: List[List[int]], origin: int) -> int:
    adj = collections.defaultdict(list)
    for u, v in lines:
        adj[u].append(v)
        adj[v].append(u)
        
    if origin not in adj and not lines:
        return 1
    if origin not in adj: return 1

    visited = set([origin])
    queue = collections.deque([origin])
    
    while queue:
        u = queue.popleft()
        for v in adj[u]:
            if v not in visited:
                visited.add(v)
                queue.append(v)
                
    return len(visited)

rust

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

pub fn power_grid_coverage(_n: i32, lines: Vec<Vec<i32>>, origin: i32) -> i32 {
    let mut adj: HashMap<i32, Vec<i32>> = HashMap::new();
    for line in lines {
        adj.entry(line[0]).or_default().push(line[1]);
        adj.entry(line[1]).or_default().push(line[0]);
    }

    if !adj.contains_key(&origin) {
        return 1;
    }

    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    
    visited.insert(origin);
    queue.push_back(origin);
    
    while let Some(u) = queue.pop_front() {
        if let Some(neighbors) = adj.get(&u) {
            for &v in neighbors {
                if visited.insert(v) {
                    queue.push_back(v);
                }
            }
        }
    }

    visited.len() as i32
}

typescript

function power_grid_coverage(n: number, lines: number[][], origin: number): number {
    const adj = new Map<number, number[]>();
    for (const [u, v] of lines) {
        if (!adj.has(u)) adj.set(u, []);
        adj.get(u)!.push(v);
        if (!adj.has(v)) adj.set(v, []);
        adj.get(v)!.push(u);
    }

    if (!adj.has(origin)) return 1;

    const visited = new Set<number>();
    visited.add(origin);
    const queue = [origin];

    while (queue.length > 0) {
        const u = queue.shift()!;
        const neighbors = adj.get(u);
        if (neighbors) {
            for (const v of neighbors) {
                if (!visited.has(v)) {
                    visited.add(v);
                    queue.push(v);
                }
            }
        }
    }
    return visited.size;
}

Comments (0)

Join the Discussion

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

Riverside Power Grid Check

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