Interstate Rescue Network Audit

Array Medium 6 views

Like19

Interstate Rescue Network Audit is a reachability count problem on an undirected road graph with selective closures. You receive the total depot count, a list of two-way highways, a starting depot, and a list of blocked highway references. Your task is to compute how many depots can still be reached from the start when those blocked routes are removed from traversal.

The reliable approach is graph traversal after filtering blocked links. Build adjacency using only open highways, then run BFS or DFS from the starting depot and count unique visited depots. Duplicate highways should not inflate counts, and disconnected components that are not connected to the origin must be ignored. If closures isolate the start, the answer is just the starting depot itself.

Judge behavior emphasizes correctness under partial shutdown conditions: chain networks cut in the middle, sparse graphs with separated islands, and cases where blocked routes leave only a tiny reachable component. Return a single integer count only. The core challenge is maintaining exact traversal constraints so every open depot is counted once and only once, while blocked links are treated as fully unavailable regardless of their direction in the original input list.

In implementation terms, treat closed-highway references consistently with the same indexing convention used by the input provider, then construct traversal edges only from allowed routes. This prevents accidental leakage through blocked links and keeps results aligned when route lists include repeated or symmetric entries.

Examples

Example 1

Input

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

Output

Explanation

Depots 0, 1, and 2 receive the alert; the closure prevents reaching the rest.

Example 2

Input

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

Output

Explanation

With no closures, the activation spreads to all depots.

Example 3

Input

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

Output

Explanation

The origin depot is surrounded by closed highways, so only itself is active.

Algorithm Flow

Recommendation Algorithm Flow for Interstate Rescue Network Audit - Budibadu

Best Answers

java

import java.util.*;
class Solution {
    public int rescue_network_reach(int n, int[][] roads, int start, int[][] closed_highways) {
        Set<String> closed = new HashSet<>();
        for (int[] r : closed_highways) {
            int u = Math.min(r[0], r[1]);
            int v = Math.max(r[0], r[1]);
            closed.add(u + "-" + v);
        }

        Map<Integer, List<Integer>> adj = new HashMap<>();
        for (int[] r : roads) {
            int u = Math.min(r[0], r[1]);
            int v = Math.max(r[0], r[1]);
            if (!closed.contains(u + "-" + v)) {
                adj.computeIfAbsent(r[0], k -> new ArrayList<>()).add(r[1]);
                adj.computeIfAbsent(r[1], k -> new ArrayList<>()).add(r[0]);
            }
        }

        Set<Integer> visited = new HashSet<>();
        Queue<Integer> queue = new LinkedList<>();
        
        visited.add(start);
        queue.offer(start);
        
        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 rescue_network_reach(n, roads, start, closed_highways) {
    const closed = new Set();
    for (const [u, v] of closed_highways) {
        closed.add(u < v ? `${u}-${v}` : `${v}-${u}`);
    }

    const adj = new Map();
    for (const [u, v] of roads) {
        const key = u < v ? `${u}-${v}` : `${v}-${u}`;
        if (!closed.has(key)) {
            if (!adj.has(u)) adj.set(u, []);
            adj.get(u).push(v);
            if (!adj.has(v)) adj.set(v, []);
            adj.get(v).push(u);
        }
    }

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

    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 rescue_network_reach($n, $roads, $start, $closed_highways) {
    $closed = [];
    foreach ($closed_highways as $h) {
        $key = ($h[0] < $h[1]) ? "$h[0]-$h[1]" : "$h[1]-$h[0]";
        $closed[$key] = true;
    }

    $adj = [];
    foreach ($roads as $r) {
        $key = ($r[0] < $r[1]) ? "$r[0]-$r[1]" : "$r[1]-$r[0]";
        if (!isset($closed[$key])) {
            $adj[$r[0]][] = $r[1];
            $adj[$r[1]][] = $r[0];
        }
    }

    $visited = [$start => true];
    $queue = [$start];
    $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 rescue_network_reach(n: int, roads: List[List[int]], start: int, closed_highways: List[List[int]]) -> int:
    closed = set()
    for u, v in closed_highways:
        closed.add(tuple(sorted((u, v))))
        
    adj = collections.defaultdict(list)
    for u, v in roads:
        if tuple(sorted((u, v))) not in closed:
            adj[u].append(v)
            adj[v].append(u)
            
    visited = {start}
    queue = collections.deque([start])
    
    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 rescue_network_reach(_n: i32, roads: Vec<Vec<i32>>, start: i32, closed_highways: Vec<Vec<i32>>) -> i32 {
    let mut closed: HashSet<(i32, i32)> = HashSet::new();
    for c in closed_highways {
        let (u, v) = if c[0] < c[1] { (c[0], c[1]) } else { (c[1], c[0]) };
        closed.insert((u, v));
    }

    let mut adj: HashMap<i32, Vec<i32>> = HashMap::new();
    for r in roads {
        let (u, v) = (r[0], r[1]);
        let key = if u < v { (u, v) } else { (v, u) };
        if !closed.contains(&key) {
            adj.entry(u).or_default().push(v);
            adj.entry(v).or_default().push(u);
        }
    }

    let mut visited = HashSet::new();
    let mut queue = VecDeque::new();
    
    visited.insert(start);
    queue.push_back(start);
    
    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 rescue_network_reach(n: number, roads: number[][], start: number, closed_highways: number[][]): number {
    const closed: { [key: string]: boolean } = {};
    for (let i = 0; i < closed_highways.length; i++) {
        const u = closed_highways[i][0];
        const v = closed_highways[i][1];
        const key = u < v ? u + "-" + v : v + "-" + u;
        closed[key] = true;
    }

    const adj: { [key: number]: number[] } = {};
    for (let i = 0; i < roads.length; i++) {
        const u = roads[i][0];
        const v = roads[i][1];
        const key = u < v ? u + "-" + v : v + "-" + u;
        if (!closed[key]) {
            if (!adj[u]) adj[u] = [];
            adj[u].push(v);
            if (!adj[v]) adj[v] = [];
            adj[v].push(u);
        }
    }

    const visited: { [key: number]: boolean } = {};
    visited[start] = true;
    const queue: number[] = [start];

    let head = 0;
    while (head < queue.length) {
        const u = queue[head];
        head++;
        const neighbors = adj[u];
        if (neighbors) {
            for (let i = 0; i < neighbors.length; i++) {
                const v = neighbors[i];
                if (!visited[v]) {
                    visited[v] = true;
                    queue.push(v);
                }
            }
        }
    }
    
    let count = 0;
    for (const k in visited) count++;
    return count;
}

Comments (0)

Join the Discussion

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

Interstate Rescue Network Audit

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