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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Reachable Nodes With Restrictions

Number: 2445

Difficulty: Medium

Paid? No

Companies: MakeMyTrip

Problem Description

Given an undirected tree with n nodes (labeled from 0 to n - 1) and n - 1 edges, determine the maximum number of nodes that are reachable from node 0 without visiting any node from a restricted set. Node 0 is guaranteed not to be restricted.

Key Insights

  • Represent the tree using an adjacency list for efficient neighbor traversal.
  • Utilize DFS or BFS starting from node 0 to explore the graph.
  • Use a set for restricted nodes to enable quick lookups.
  • Maintain a visited set (or equivalent) to avoid revisiting nodes.
  • Since the structure is a tree, no extra cycle detection is required.

Space and Time Complexity

Time Complexity: O(n) as each node and edge is visited at most once.
Space Complexity: O(n) due to the adjacency list storage and the visited/restricted sets.

Solution

The problem is solved by performing a DFS or BFS traversal from node 0. First, convert the list of edges into an adjacency list. Then initialize a set for restricted nodes for O(1) access. Start the traversal from node 0 and maintain a visited set to prevent reprocessing nodes. For each node encountered, add its neighbors to the stack (or queue) if they have not been visited and are not restricted. Count the number of nodes visited during the traversal to determine the maximum reachable nodes.

Code Solutions

# Define a function using DFS to count reachable nodes.
def reachableNodes(n, edges, restricted):
    # Build the adjacency list from edges.
    graph = {i: [] for i in range(n)}
    for u, v in edges:
        graph[u].append(v)
        graph[v].append(u)
    
    # Convert restricted list to a set for O(1) lookups.
    restricted_set = set(restricted)
    
    # Initialize visited set and DFS stack.
    visited = set()
    stack = [0]
    visited.add(0)
    
    reachable_count = 0
    
    while stack:
        node = stack.pop()
        reachable_count += 1
        # Traverse each neighbor.
        for neighbor in graph[node]:
            if neighbor not in visited and neighbor not in restricted_set:
                visited.add(neighbor)
                stack.append(neighbor)
    
    return reachable_count

# Example usage:
n = 7
edges = [[0,1],[1,2],[3,1],[4,0],[0,5],[5,6]]
restricted = [4,5]
print(reachableNodes(n, edges, restricted))  # Expected output: 4
← Back to All Questions