n개의 꼭짓점과 노드가 0에서 n-1까지 번호가 매겨진 방향성 비순환 그래프가 있다고 가정하고 그래프는 에지 목록으로 표시됩니다. 여기서 edge[i] =(u, v)는 노드 u에서 n-1까지의 방향성 에지를 나타냅니다. 노드 v. 그래프의 모든 노드에 도달할 수 있는 가장 작은 정점 집합을 찾아야 합니다. (정점을 임의의 순서로 반환할 수 있습니다.)
따라서 입력이 다음과 같으면
이 두 정점은 다른 정점에서 도달할 수 없기 때문에 출력은 [0,2,3]이 됩니다. 따라서 이 정점에서 시작하면 모두를 포함할 수 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
-
n :=가장자리 크기
-
all_nodes :=범위 0에서 n까지의 새 세트
-
v :=새로운 세트
-
에지의 각 에지(i, j)에 대해 수행
-
v에 j 추가
-
-
ans :=all_nodes에서 모든 공통 가장자리를 제거하고 all_nodes에서 v를 제거합니다.
-
반환
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
def solve(edges): n = len(edges) all_nodes = set(range(n)) v = set() for edge in edges: v.add(edge[1]) ans = all_nodes - v return ans edges = [(0,1),(2,1),(3,1),(1,4),(2,4)] print(solve(edges))
입력
[(0,1),(2,1),(3,1),(1,4),(2,4)]
출력
{0, 2, 3}