有向非巡回グラフ内のノードのすべての祖先

2192年。有向非巡回グラフ内のノードのすべての祖先

中

有向非巡回グラフ (DAG) のノード数を表す正の整数 n が与えられます。ノードには 0 から n - 1 (を含む) までの番号が付けられます。

2D 整数配列のエッジも与えられます。ここで、edges[i] = [from_i, to_i] は、一方向があることを示します。グラフ内の from_i から to_i までのエッジ。

リストの回答を返します。ここで、answer[i] は、昇順でソートされた、i​​^番目ノードの先祖のリストです。

一連のエッジを介して v に到達できる場合、ノード u は別のノード 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 には 2 つの祖先 0 と 1 があります。
  • ノード 4 には 2 つの祖先 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 には 1 つの祖先 0 があります。
  • ノード 2 には 2 つの祖先 0 と 1 があります。
  • ノード 3 には 3 つの祖先 0、1、2 があります。
  • ノード 4 には 4 つの祖先 0、1、2、および 3 があります。

制約:

• 1
• 0
• edges[i].length == 2
• 0 _iから、_iまで
i
• <= n - 1 から_i != から
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);
            }
        }
    }
}







連絡先リンク





LinkedIn

GitHub



          

            
  

            
        
以上が有向非巡回グラフ内のノードのすべての祖先の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。