1
class Solution:
2
    def reachableNodes(
3
        self, n: int, edges: List[List[int]], restricted: List[int]
4
    ) -> int:
5
        # ignore restricted node
6
        # bfs from 0
7

8
        # O(E), EDITED: the time complexity here is wrong, plz see my comment
9
        adj_dict = collections.defaultdict(list)
10
        for u, v in edges:
11
            if u in restricted or v in restricted:  # EDITED: not O(1)
12
                continue
13
            adj_dict[u].append(v)
14
            adj_dict[v].append(u)
15

16
        # O(V + E)
17
        queue = collections.deque([0])
18
        visited = {0}
19
        while queue:
20
            cur = queue.popleft()
21
            for neighbor in adj_dict[cur]:
22
                if neighbor in visited:
23
                    continue
24
                visited.add(neighbor)
25
                queue.append(neighbor)
26

27
        return len(visited)