algorithm - 接続されていない有向グラフ頂点の最大サブセットのサイズ？

Question

有向グラフが与えられた場合、それらの2つが有向パスで接続されないように、頂点の最大サブセットのサイズをどのように見つけることができますか？

この問題（またはそれを解決するアルゴリズム）には共通の名前がありますか？

（ヒント：「ディルワースの定理によれば、この問題は、推移閉包を計算した後のDAGでカバーされるチェーンの最小数と実際に同等です。したがって、この問題は2部グラフで最大の一致に減らすことができます。」）

Answer 1

名前はわかりませんが、Disjoint-set データ構造のサブ問題だと思います

Union Find を使用すると、接続されたすべてのグラフを決定できます。

最初は、各ノードはそのグループにあります。すべてのノードを確認し、そのすべての直接の子をノードのグループ ルートに追加します。これは基本的な Union Find です。

最大のサブセットは、各グループの 1 つの頂点で構成されます。

最悪の場合、すべてのノードが他のすべてのノードに接続されている場合、すべてのノードが n 回チェックされるため、O(n²) かかります。