We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Reachable Nodes With Restrictions

Difficulty: Medium

Problem Description

You are given an undirected tree with n nodes labeled from 0 to n - 1 and n - 1 edges. You also have a 2D integer array edges representing the edges of the tree and an integer array restricted representing restricted nodes. The task is to return the maximum number of nodes you can reach from node 0 without visiting a restricted node.

Key Insights

  • The tree structure allows for traversal using Depth-First Search (DFS) or Breadth-First Search (BFS).
  • Nodes in the restricted list cannot be visited during traversal, effectively limiting the reachable nodes.
  • The problem can be visualized as a graph traversal problem where certain vertices are blocked.

Space and Time Complexity

Time Complexity: O(n), where n is the number of nodes. Each node and edge is processed once during traversal. Space Complexity: O(n), due to the space required to store the adjacency list and the visited nodes.

Solution

To solve this problem, we can use a graph traversal algorithm, such as Depth-First Search (DFS) or Breadth-First Search (BFS). We will represent the tree using an adjacency list to facilitate efficient traversal.

  1. Build an adjacency list from the edges.
  2. Create a set of restricted nodes for quick look-up.
  3. Use DFS or BFS starting from node 0, skipping any restricted nodes.
  4. Count the number of nodes visited during the traversal.

This approach ensures that we explore all reachable nodes while respecting the restrictions imposed by the restricted nodes.

Code Solutions

def reachableNodes(n, edges, restricted):
    from collections import defaultdict
    
    # Step 1: Build the adjacency list
    graph = defaultdict(list)
    for a, b in edges:
        graph[a].append(b)
        graph[b].append(a)

    # Step 2: Create a set of restricted nodes
    restricted_set = set(restricted)

    # Step 3: Perform DFS
    def dfs(node):
        if node in restricted_set or node in visited:
            return 0
        visited.add(node)
        count = 1  # Count this node
        for neighbor in graph[node]:
            count += dfs(neighbor)  # Sum reachable nodes from neighbors
        return count

    visited = set()
    return dfs(0)  # Start DFS from node 0
← Back to All Questions