[릿코드 1557] Minimum Number of Vertices to Reach All Nodes (파이썬/python)

https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/description/

 

양방향 그래프가 아닌 단방향 그래프기떄문에
다른 노드를 통해서 도달하지 못 하는 노드가 있습니다.
이 노드들만을 이용해서 모든 그래프를 순회할 수 있습니다. ( 다른 노드들이 서로 연결되어있을것이기 때문에)

그렇기 때문에 이 노드들을 모아 리턴하면됩니다.

다른 노드를 통해 접근할 수 있는 노드는 애초에 정답의 대상이 되지 못 합니다

 

class Solution:

    def findSmallestSetOfVertices(self, n: int, edges: List[List[int]]) -> List[int]:
        reachable = set()
        for edge in edges:
            reachable.add(edge[1])

        not_reachable= []
        for i in range(n):
            if i not in reachable:
                not_reachable.append(i)

        return not_reachable