Interstate Rescue Network Audit

Published at05 Jan 2026

Graph BFS Medium 30 views

Like19

This challenge becomes much easier once you know exactly what to keep, change, or count. In Interstate Rescue Network Audit, you are trying to work toward the right number by following one clear idea.

Here, you are mostly deciding whether a rule stays true while you look through the input. Sometimes that means checking if things are connected, balanced, or allowed. Sometimes it means noticing the first place where the rule breaks. The answer depends on being careful from beginning to end.

For example, if the input is n = 6, roads = [[0,1],[1,2],[2,3],[3,4],[4,5]], start = 0, closed_highways = [[2,3]], the answer is 3. Depots 0, 1, and 2 receive the alert; the closure prevents reaching the rest. Another example is n = 5, roads = [[0,1],[1,2],[2,3],[3,4]], start = 4, closed_highways = [], which gives 5. With no closures, the activation spreads to all depots.

This problem needs a little more patience than a very easy one. The key is noticing the exact moment when the rule stays true or breaks.

Example Input & Output

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

Solution Approach

This problem asks us to count how many depots the rescue alert can reach, excluding certain closed highways. The roads form an undirected graph, and we must build the graph while skipping any edge that is listed as closed, then count the connected component of the start.

The key detail is that a closed highway must be identified regardless of the order of its two endpoints. Since roads are undirected, we normalize each edge to a canonical key (the smaller node first) so we can check membership reliably.

Here is the implementation:

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;
}

First we build a set of closed-highway keys, normalizing each pair so [2,3] and [3,2] are treated identically. Then we build the adjacency map from the open roads only, skipping any edge whose key is in the closed set. Finally we run BFS from the start and count visited nodes.

Let us trace n = 6, roads = [[0,1],[1,2],[2,3],[3,4],[4,5]], start = 0, closed_highways = [[2,3]]. The edge [2,3] is closed, so the graph splits into {0,1,2} and {3,4,5}. From depot 0, we reach 1 and 2, giving 3. With no closures, all depots are reachable and the answer is 5.

The time complexity is O(n + e) and the space complexity is O(n).

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

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;
}

Related Graph Challenges

Comments (0)

Join the Discussion

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

Interstate Rescue Network Audit

Example Input & Output

Algorithm Flow

Solution Approach

Best AnswersThese are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.

Solutions Coming Soon

Related Graph Challenges

Wildlife Bridge Network Scan

Metro Transfer Capacity Map

City Signal Span

Memory Rune Sequencer

Shortest Path in Weighted Graph

Campus Shuttle Path with Dijkstra

Comments (0)

Join the Discussion

Best Answers
These are the verified best solutions for this Challenge. You can use them as a reference to improve your solution.