Rumah > pembangunan bahagian belakang > tutorial php > Semua Nenek Moyang Nod dalam Graf Akiklik Terarah

Semua Nenek Moyang Nod dalam Graf Akiklik Terarah

WBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWBOYWB
Lepaskan: 2024-07-17 19:34:52
asal
520 orang telah melayarinya

2192. Semua Nenek Moyang Nod dalam Graf Akiklik Berarah

Sederhana

Anda diberi integer positif n mewakili bilangan nod Graf Akiklik Berarah (DAG). Nod bernombor dari 0 hingga n - 1 (inklusif).

Anda juga diberikan tepi tatasusunan integer 2D, di mana tepi[i] = [darii, hinggai] menandakan bahawa terdapat satu arah tepi darii kei dalam graf.

Kembalikan jawapan senarai, dengan jawapan[i] ialah senarai nenek moyang nod ike, diisih dalam tertib menaik.

Nod u ialah nenek moyang nod v lain jika anda boleh mencapai v melalui set tepi.

Contoh 1:

All Ancestors of a Node in a Directed Acyclic Graph

  • Input: n = 8, edgeList = [[0,3],[0,4],[1,3],[2,4],[2,7],[3,5] ,[3,6],[3,7],[4,6]]
  • Output: [[],[],[],[0,1],[0,2],[0,1,3],[0,1,2,3,4], [0,1,2,3]]
  • Penjelasan: Gambar rajah di atas mewakili graf input.
    • Nod 0, 1 dan 2 tidak mempunyai sebarang nenek moyang.
    • Nod 3 mempunyai dua nenek moyang 0 dan 1.
    • Nod 4 mempunyai dua nenek moyang 0 dan 2.
    • Nod 5 mempunyai tiga moyang 0, 1 dan 3.
    • Nod 6 mempunyai lima moyang 0, 1, 2, 3 dan 4.
    • Nod 7 mempunyai empat nenek moyang 0, 1, 2 dan 3.

Contoh 2:

All Ancestors of a Node in a Directed Acyclic Graph

  • Input: n = 5, edgeList = [[0,1],[0,2],[0,3],[0,4],[1,2],[1,3] ,[1,4],[2,3],[2,4],[3,4]]
  • Output: [[],[0],[0,1],[0,1,2],[0,1,2,3]]
  • Penjelasan: Gambar rajah di atas mewakili graf input.
    • Nod 0 tidak mempunyai sebarang moyang.
    • Nod 1 mempunyai satu moyang 0.
    • Nod 2 mempunyai dua nenek moyang 0 dan 1.
    • Nod 3 mempunyai tiga moyang 0, 1 dan 2.
    • Nod 4 mempunyai empat nenek moyang 0, 1, 2 dan 3.

Kekangan:

  • 1 <= n <= 1000
  • 0 <= edges.length <= min(2000, n * (n - 1) / 2)
  • tepi[i].panjang == 2
  • 0 <= daripadai, kepadai <= n - 1
  • darii != kepadai
  • Tiada pendua tepi.
  • Graf adalah diarahkan dan asiklik.

Penyelesaian:

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




Pautan Kenalan

  • LinkedIn
  • GitHub

Atas ialah kandungan terperinci Semua Nenek Moyang Nod dalam Graf Akiklik Terarah. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!

Kenyataan Laman Web ini
Kandungan artikel ini disumbangkan secara sukarela oleh netizen, dan hak cipta adalah milik pengarang asal. Laman web ini tidak memikul tanggungjawab undang-undang yang sepadan. Jika anda menemui sebarang kandungan yang disyaki plagiarisme atau pelanggaran, sila hubungi admin@php.cn
Tutorial Popular
Lagi>
Muat turun terkini
Lagi>
kesan web
Kod sumber laman web
Bahan laman web
Templat hujung hadapan