0

n 個のノードとn個のエッジを持つ無向連結グラフが与えられます。2 つのノードaとbが与えられます。a から b へのパスにあるが、サイクルの一部ではないエッジの数を見つけます。（エッジの数がnであるため、確かにサイクルがあります）。これは dsu データ構造によって実行できますか? エッジを削除すると a と b が切断される場合、それを答えとして数えることができます。前もって感謝します。

4

1 に答える 1

1

もちろん、おっしゃったように DSU を介して問題を解決することはできますが、解決策は十分に効率的ではありません。DSU はエッジの削除が苦手なので、DSU を使用して問題を解決したい場合は、

for e in E
   use E-e to construct a DSU
   check the connectivity of a and b

ランク手法によるパスの圧縮とマージを使用して DSU を実装した場合でも、1 つのクエリの時間計算量は O(n^2a(n)) です。ここで、a(n) は反アッカーマン関数です。それは受け入れられません。

どうしてもエッジの列挙と削除で問題を解決したい場合は、O(logn) 時間でエッジを削除または追加できるリンク カット ツリーをお勧めします。このようにして、O(nlogn) 時間でクエリに答えることができます。

ただし、前処理ジョブを実行すると、各クエリに O(1) 時間で応答できる、非常に効率的なアルゴリズムがいくつか存在します。グラフは特別です: n個の頂点とn個の辺を持つ接続されたグラフには1 つのサイクルしかありません。このグラフは t 個の頂点を持つサイクルと見なすことができ、各頂点はツリーのルートです。そのため、前処理中に dfs を使用して、各頂点が属するツリーと各頂点の深さを計算します (対応するツリーでは、各ルートの深さは 0 です)。さらに、O(1) 時間で LCA を照会するために、tarjan アルゴリズムを使用して各ツリーを前処理します。

次に、2 つの頂点uとが与えられた各クエリvについて、最初にそれらが同じツリーにあるかどうかを確認します。次の 2 つの状況があります。

  • u答えが「はい」の場合、それらの間の最短経路は完全にツリーの内側にあるため、 との間の距離を計算するだけでvよく、明らかに、最短距離は深さ (u) + 深さ (v) -2*深さ (LCA) です。
  • 答えが「いいえ」の場合、 と の間のパスはu3vつの部分に分けることができます。最初の部分はツリー (u) にあり、2 番目の部分はサイクル上にあり、3 番目の部分はツリー (v) にあります。この場合、ツリー内のエッジの数は単純に深さ (u) + 深さ (v) です。

上記のアルゴリズムを適用することにより、O(n) 時間の複雑さの前処理と、各クエリの O(1) 時間の複雑さを通じて問題を解決できます。qクエリがありq、非常に大きい場合、このアルゴリズムはその利点を発揮します。

于 2021-08-25T09:09:09.247 に答える