LC-2368 Medium LeetCode

2368. Reachable Nodes With Restrictions

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

Read the full problem statement on LeetCode.

Difficulty: medium Acceptance: 59% Topics: Array, Hash Table, Tree, Depth-First Search, Breadth-First Search, Union Find, Graph

View full problem on LeetCode

Reading material

Arrays & Hashing 12 min Trees & Traversals 18 min Union–Find (DSU) 12 min

Reference solution (spoiler · python)

# Time:  O(n)
# Space: O(n)

# bfs
class Solution(object):
    def reachableNodes(self, n, edges, restricted):
        """
        :type n: int
        :type edges: List[List[int]]
        :type restricted: List[int]
        :rtype: int
        """
        adj = [[] for _ in xrange(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)
        result = 0
        lookup = [False]*n
        for x in restricted:
            lookup[x] = True
        q = [0]
        lookup[0] = True
        while q:
            new_q = []
            for u in q:
                result += 1
                for v in adj[u]:
                    if lookup[v]:
                        continue
                    lookup[v] = True
                    new_q.append(v)
            q = new_q
        return result

Solution from kamyu104/LeetCode-Solutions · MIT