Disaster Relief Route Tracker

Array Medium 0 views

Like17

Disaster Relief Route Tracker is a connectivity count problem with blocked shelters. You get the number of shelters, undirected roads, a start shelter, and a list of blocked shelter IDs. Count how many open shelters are reachable from the start without passing through blocked shelters.

Build graph adjacency, mark blocked shelters, and run BFS or DFS while skipping blocked nodes. If the start is blocked, reachability is zero in a strict interpretation; in this dataset the start is open in tested cases, and traversal should count each reachable open shelter once. Duplicate roads should not create duplicate visits, so maintain a visited set throughout the traversal.

Judge scenarios include partially blocked graphs, disconnected components, and cases where one blocked hub sharply reduces coverage. Return only the integer count. The important implementation detail is node-level blocking (shelters), not edge-level blocking, so checks happen before visiting nodes and when iterating neighbors. With clean filtering and one traversal pass, the result stays deterministic and consistent across sparse and dense road maps.

Keep blocked-shelter checks on both queue insertion and neighbor expansion so blocked nodes are never traversed indirectly. This ensures computed coverage matches operational rules where closed shelters cannot relay routes, even if they still appear in adjacency lists from raw road data.

Examples

Example 1

Input

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

Output

Explanation

The convoy reaches shelters 1, 0, 2, 3, and 5 while skipping the blocked shelter 4.

Example 2

Input

n = 4, roads = [], start = 2, blocked_shelters = []

Output

Explanation

With no roads, only the staging shelter receives supplies.

Example 3

Input

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

Output

Explanation

The convoy can only deliver to shelters 0 and 1 before encountering a blocked location.

Algorithm Flow

Recommendation Algorithm Flow for Disaster Relief Route Tracker - Budibadu

Best Answers

java

import java.util.*;

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

javascript

function disaster_relief_route_tracker(n, roads, start, blocked_shelters) {
    const blocked = new Set(blocked_shelters);
    if (blocked.has(start)) return 0;
    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 u = queue.shift();
        for (const v of adj[u]) {
            if (!visited.has(v) && !blocked.has(v)) {
                visited.add(v);
                queue.push(v);
            }
        }
    }
    return visited.size;
}

php

<?php
function disaster_relief_route_tracker($n, $roads, $start, $blocked_shelters) {
    $blocked = array_flip($blocked_shelters);
    if (isset($blocked[$start])) return 0;
    $adj = array_fill(0, $n, []);
    foreach ($roads as $road) {
        $u = $road[0];
        $v = $road[1];
        $adj[$u][] = $v;
        $adj[$v][] = $u;
    }
    $visited = [$start => true];
    $queue = [$start];
    while (!empty($queue)) {
        $u = array_shift($queue);
        foreach ($adj[$u] as $v) {
            if (!isset($visited[$v]) && !isset($blocked[$v])) {
                $visited[$v] = true;
                $queue[] = $v;
            }
        }
    }
    return count($visited);
}
?>

python

from typing import List
from collections import deque

def disaster_relief_route_tracker(n: int, roads: List[List[int]], start: int, blocked_shelters: List[int]) -> int:
    blocked = set(blocked_shelters)
    if start in blocked: return 0
    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:
        u = queue.popleft()
        for v in adj[u]:
            if v not in visited and v not in blocked:
                visited.add(v)
                queue.append(v)
    return len(visited)

rust

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

pub fn disaster_relief_route_tracker(n: i32, roads: Vec<Vec<i32>>, start: i32, blocked_shelters: Vec<i32>) -> i32 {
    let blocked: HashSet<i32> = blocked_shelters.into_iter().collect();
    if blocked.contains(&start) { return 0; }
    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 as i32);
        adj[v].push(u as i32);
    }
    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    visited.insert(start);
    queue.push_back(start);
    while let Some(u) = queue.pop_front() {
        for &v in &adj[u as usize] {
            if !visited.contains(&v) && !blocked.contains(&v) {
                visited.insert(v);
                queue.push_back(v);
            }
        }
    }
    visited.len() as i32
}

typescript

function disaster_relief_route_tracker(n: number, roads: number[][], start: number, blocked_shelters: number[]): number {
    const blocked = new Set(blocked_shelters);
    if (blocked.has(start)) return 0;
    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<number>([start]);
    const queue: number[] = [start];
    while (queue.length > 0) {
        const u = queue.shift()!;
        for (const v of adj[u]) {
            if (!visited.has(v) && !blocked.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.

Disaster Relief Route Tracker

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