#2368

Reachable Nodes With Restrictions

specialist · 710 · lc medium +30 · verified · 60.2% accepted · 770 likes · top 59%

⚑ DFS / BFS: Connected Components & Reachability

Description

An undirected tree of n nodes (labeled 0 to n - 1) is described by a 2D array edges where edges[i] = [ai, bi] denotes an edge. An integer array restricted lists nodes that cannot be visited.

Starting from node 0 (which is never restricted), find and return the maximum number of nodes reachable without passing through any restricted node.

Example 1:

Input: n = 7, edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]], restricted = [4,5]

Output: 4

Explanation: The diagram above shows the tree.

We have that [0,1,2,3] are the only nodes that can be reached from node 0 without visiting a restricted node.

Example 2:

Input: n = 7, edges = [[0,1],[0,2],[0,5],[0,4],[3,2],[6,5]], restricted = [4,2,1]

Output: 3

Explanation: The diagram above shows the tree.

We have that [0,5,6] are the only nodes that can be reached from node 0 without visiting a restricted node.

Code

1

2

3

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int:

class Solution:
    def reachableNodes(self, n: int, edges: List[List[int]], restricted: List[int]) -> int: