Time and Space Complexity

時間計算量:

• E 個の辺のソートは O(E log E) です。経路圧縮を用いた各 union-find 操作はほぼ O(1) であるため、標準的なクラスカル法は O(E log E) となります。ここで構築する最小選択バージョンは O(E²) ですが、これは小さなグラフであれば問題ありません。

空間計算量:

• parent 配列（および入力の辺）のために O(V) です。

まとめ:

• クラスカル法は、union-find を使用してサイクルの有無を判定しながら、各ステップでサイクルを作らない最も安価な辺を追加することで最小全域木（MST）を構築します。
• すべての最小全域木は同じ総重みを共有するため、答えは一意になります。