Alle Vorfahren eines Knotens in einem gerichteten azyklischen Graphen

2192. Alle Vorfahren eines Knotens in einem gerichteten azyklischen Graphen

Mittel

Sie erhalten eine positive ganze Zahl n, die die Anzahl der Knoten eines Gerichteten Azyklischen Graphen (DAG) darstellt. Die Knoten sind von 0 bis n - 1 (einschließlich) nummeriert.

Sie erhalten außerdem ein ganzzahliges 2D-Array mit Kanten, wobei Kanten[i] = [von_i, bis_i] angibt, dass es eine unidirektionale gibt Kante von von_i bis zu_i im Diagramm.

Eine Listenantwort zurückgeben, wobei Antwort[i] die Liste der Vorfahren des i^ten Knotens ist, sortiert in aufsteigender Reihenfolge.

Ein Knoten u ist ein Vorfahre eines anderen Knotens v, wenn u über eine Reihe von Kanten v erreichen kann.

Beispiel 1:

• Eingabe: n = 8, EdgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5] ,[3,6],[3,7],[4,6]]
• Ausgabe: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4], [0,1,2,3]]
• Erklärung: Das obige Diagramm stellt das Eingabediagramm dar.
  • Knoten 0, 1 und 2 haben keine Vorfahren.
  • Knoten 3 hat zwei Vorfahren 0 und 1.
  • Knoten 4 hat zwei Vorfahren 0 und 2.
  • Knoten 5 hat drei Vorfahren 0, 1 und 3.
  • Knoten 6 hat fünf Vorfahren: 0, 1, 2, 3 und 4.
  • Knoten 7 hat vier Vorfahren: 0, 1, 2 und 3.

Beispiel 2:

• Eingabe: n = 5, EdgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3] ,[1,4],[2,3],[2,4],[3,4]]
• Ausgabe: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
• Erklärung: Das obige Diagramm stellt das Eingabediagramm dar.
  • Knoten 0 hat keinen Vorfahren.
  • Knoten 1 hat einen Vorfahren 0.
  • Knoten 2 hat zwei Vorfahren 0 und 1.
  • Knoten 3 hat drei Vorfahren 0, 1 und 2.
  • Knoten 4 hat vier Vorfahren: 0, 1, 2 und 3.

Einschränkungen:

• 1 <= n <= 1000
• 0 <= Kanten.Länge <= min(2000, n * (n - 1) / 2)
• edges[i].length == 2
• 0 <= von_i, bis_i <= n - 1
• von_i != bis_i
• Es gibt keine doppelten Kanten.
• Der Graph ist gerichtet und azyklisch.

Lösung:

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);
            }
        }
    }
}




Kontaktlinks


LinkedIn
GitHub



          

            
  

            
        
Das obige ist der detaillierte Inhalt vonAlle Vorfahren eines Knotens in einem gerichteten azyklischen Graphen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!