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

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

중간

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

또한 2D 정수 배열 가장자리가 제공됩니다. 여기서 edge[i] = [from_i, to_i]는 단방향이 있음을 나타냅니다. 그래프의 _i에서 _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에는 0, 1, 2, 3, 4라는 5개의 상위 항목이 있습니다.
  • 노드 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에는 3개의 상위 항목 0, 1, 2가 있습니다.
  • 노드 4에는 4개의 상위 항목 0, 1, 2, 3이 있습니다.

제약조건:

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

해결책:

class Solution {

    /**
     * @param Integer $n
     * @param Integer[][] $edges
     * @return Integer[][]
     */
    function getAncestors($n, $edges) {
        $adjacencyList = array_fill(0, $n, []);
        foreach ($edges as $edge) {
            $from = $edge[0];
            $to = $edge[1];
            $adjacencyList[$to][] = $from;
        }

        $ancestorsList = [];

        for ($i = 0; $i < $n; $i++) {
            $ancestors = [];
            $visited = [];
            $this->findChildren($i, $adjacencyList, $visited);
            for ($node = 0; $node < $n; $node++) {
                if ($node == $i) continue;
                if (in_array($node, $visited))
                    $ancestors[] = $node;
            }
            $ancestorsList[] = $ancestors;
        }

        return $ancestorsList;
    }

    private function findChildren($currentNode, &$adjacencyList, &$visitedNodes) {
        $visitedNodes[] = $currentNode;
        foreach ($adjacencyList[$currentNode] as $neighbour) {
            if (!in_array($neighbour, $visitedNodes)) {
                $this->findChildren($neighbour, $adjacencyList, $visitedNodes);
            }
        }
    }
}




연락처 링크


링크드인
깃허브



          

            
  

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