방향성 비순환 그래프에 있는 노드의 모든 상위 요소

2192. 방향성 비순환 그래프에 있는 노드의 모든 조상

중간

방향성 비순환 그래프(DAG)의 노드 수를 나타내는 양의 정수 n이 제공됩니다. 노드 번호는 0부터 n - 1(포함)까지입니다.

2D 정수 배열 가장자리도 제공됩니다. 여기서 edge[i] = [from_i, to_i]는 그래프에 fromi에서 to_i까지 _단방향 가장자리가 있음을 나타냅니다. .

목록 답변을 반환합니다. 여기서 답변[i]는 i번째 노드의 ^{조상 목록}이며 오름차순으로 정렬됩니다.

노드 u는 일련의 간선을 통해 v에 도달할 수 있는 경우 다른 노드 v의 조상입니다.

예 1:

• 입력: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5],[3, 6],[3,7],[4,6]]
• 출력: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4],[0,1 ,2,3]]
• 설명: 위 다이어그램은 입력 그래프를 나타냅니다.
  • 노드 0, 1, 2에는 조상이 없습니다.
  • 노드 3에는 두 개의 조상 0과 1이 있습니다.
  • 노드 4에는 두 개의 조상 0과 2가 있습니다.
  • 노드 5에는 3개의 조상 0, 1, 3이 있습니다.
  • 노드 6에는 5개의 조상 0, 1, 2, 3, 4가 있습니다.
  • 노드 7에는 4개의 조상 0, 1, 2, 3이 있습니다.

예 2:

• 입력: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3],[1, 4],[2,3],[2,4],[3,4]]
• 출력: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
• 설명: 위 다이어그램은 입력 그래프를 나타냅니다.
  • 노드 0에는 조상이 없습니다.
  • 노드 1에는 하나의 조상 0이 있습니다.
  • 노드 2에는 두 개의 조상 0과 1이 있습니다.
  • 노드 3에는 세 개의 조상 0, 1, 2가 있습니다.
  • 노드 4에는 4개의 조상 0, 1, 2, 3이 있습니다.

제약조건:

• 1
• 0 <= edge.length <= min(2000, n * (n - 1) / 2)
• 가장자리[i].length == 2
• 0 <= from_i, to_i <= n - 1
• from_i != to_i
• 중복된 가장자리가 없습니다.
• 그래프는 방향 및 비순환입니다.

해결책:

연락처 링크

• LinkedIn
• GitHub

위 내용은 방향성 비순환 그래프에 있는 노드의 모든 상위 요소의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!