G =（V、E）を重み付きの接続された無向グラフとし、eをEの任意のエッジとします。エッジeを含む最小全域木が存在するかどうかを決定する線形時間アルゴリズムを示します。
私は質問1の奇妙な「解決策」を見つけることができました。それはうまくいくようですが、線形ではないと思います。
彼らは、W（u、v）<W（e）となるように、各エッジ（u、v）に対してunion find and do Union（u、v）を使用することを提案しました。ここで、e =（x、y）と仮定します。ここで、find（x）！= find（y）の場合、xとyは接続されておらず、W（e）はクラスカルのアルゴリズムによって調べられる次の重みになるため、エッジを含むMSTが確実に存在します。 e。
一方、find（x）= find（y）の場合、この時点までクラスカルアルゴリズムを実行すると、xとyが確実に接続されるため、エッジeをMSTに追加することはできません（重みが等しいエッジの並べ替え順序-クラスカルのアルゴリズムを使用して、任意のMSTを作成できます）。
なぜこれが線形なのかわかりませんか？組合のせいでO（| E | alpha（| V |））の費用がかかるのではないですか？
おそらく、線形時間でこれを行う別の方法がありますか？
前もって感謝します