Reachable nodes with restrictions

Array Hash Table Tree Depth-First Search Breadth-First Search Union-Find Graph Theory

60.2% acceptance

Feb 25, 2026

770

There is an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You are given a 2D integer array edges of length n - 1 where edges[i] = [ai, bi] indicates that there is an edge between nodes ai and bi in the tree. You are also given an integer array restricted which represents restricted nodes. Return the maximum number of nodes you can reach from node 0 without visiting a restricted node. Note that node 0 will not be a restricted node.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

use std::collections::VecDeque;


impl Solution {
  pub fn reachable_nodes(n: i32, edges: Vec<Vec<i32>>, restricted: Vec<i32>) -> i32 {
    let n = n as usize;
    let mut adj = vec![vec![]; n];
    for e in &edges {
      adj[e[0] as usize].push(e[1] as usize);
      adj[e[1] as usize].push(e[0] as usize);
    }
    let mut blocked = vec![false; n];
    for r in restricted { blocked[r as usize] = true; }
    let mut visited = vec![false; n];
    let mut queue = VecDeque::new();
    queue.push_back(0usize);
    visited[0] = true;
    let mut count = 0;
    while let Some(u) = queue.pop_front() {
      count += 1;
      for &v in &adj[u] {
        if !visited[v] && !blocked[v] {
          visited[v] = true;
          queue.push_back(v);
        }
      }
    }
    count
  }
}