BudiBadu Logo

Riverside Power Grid Check

Array Easy 2 views
Like14

The riverside utility district monitors a network of electrical substations linked by power lines that allow maintenance crews to traverse either direction. Each substation carries an ID between 0 and n - 1, and the grid engineers maintain a map of every line connecting two substations. When crews begin a safety check from a specific origin, they follow the available lines to inspect neighboring substations, extending the inspection outward until every reachable substation has been verified. The district wants an automated way to tell how many substations receive attention during each tour.

Create a function that accepts the total number of substations n, the list of power lines, and the origin substation origin. Each line is stored as [u, v], representing a two-way physical link between substations u and v. The mapping may include repeated entries or appear to loop from a substation back to itself if backup connections were recorded. During the inspection, once a substation has been visited, the crews do not count it again, even if alternative routes lead back to the same location.

The function should return the total number of unique substations checked, including the origin. Sections of the grid that are disconnected from origin remain unchecked. If no lines leave origin, the inspection covers only that substation. If the grid is fully connected, the crews verify every substation in a single run. Output the coverage count as a plain integer with no additional formatting.

Example 1:

Input: n = 5, lines = [[0,1],[1,2],[2,3],[3,4]], origin = 0
Output: 5
Explanation: The crew moves sequentially across each line and inspects every substation.

Example 2:

Input: n = 6, lines = [[0,1],[1,2],[0,2],[3,4]], origin = 3
Output: 2
Explanation: Only substations 3 and 4 are reachable from the origin segment.

Example 3:

Input: n = 4, lines = [], origin = 2
Output: 1
Explanation: With no power lines connected, only the origin substation is inspected.

Algorithm Flow

Recommendation Algorithm Flow for Riverside Power Grid Check - Budibadu
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();
    }
}