サイクルとフォレストを持つ有向グラフの効率的なUnion-Find (別名Disjoint Set ) データ構造を探しています。このようなグラフが与えられた場合、次のクエリに答えたいと思います。G
vからノードに到達できますuか?- 到達できないノード
uはどれですか?
単一の「ソース」ノードの場合、 DFS検索をu実行して、そこから到達できるかどうかを確認できます。1 回の DFS 検索の上限コストは、最悪の場合 です。ここで、とは、それぞれグラフ内の頂点とエッジの数です。ただし、私はそのような「ソース」ノードを多数持っており、すべての「ソース」ノードから個別に DFS を実行するよりも優れたアプローチがあるかどうか疑問に思っています (最悪の場合、上限コストはです)。vm + nmnmm * (m + n)
これらの質問の両方は、有向グラフの Union-Find データ構造によって効率的に回答できるようです。驚いたことに、かなりのオンライン検索を行っても解決策が見つかりませんでした。問題を間違った方向に考えていますか？
この答えを見つけましたが、理解できませんでした。