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

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

中

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

i_{, to}i_{] は、グラフ内に from}i から toi _までの 一方向 _{エッジがあることを示します。 .}

昇順でソートされた、i​​ 番目のノードの^{祖先のリスト}です。 エッジのセットを介して v に到達できる場合、ノード u は別のノード v の先祖

例1:

入力:

• 出力: [[],[],[],[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:

入力:

• 出力: [[],[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

連絡先リンク

リンクトイン

• GitHub

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