How it works?

Union-findは、parent配列を保持します。各頂点は、自分自身をルートとして開始します。2つの操作がすべてを制御します：

• find(x): ルート（自分自身が親である頂点）に到達するまで、parentのリンクを辿ります。2つの頂点は、ルートを共有しているときに接続されているとみなされます。
• union(a, b): 一方のルートを他方のルートに向け、2つの集合を統合します。

クラスカル法（Kruskal's Algorithm）：

1. 辺を重みの小さい順から大きい順に処理します。
2. 各辺について、その端点のルートをfindします。ルートが異なる場合、その辺は2つの独立した部分を結合します。それらをunionし、その重みを合計に加算します。
3. ルートが同じ場合、その辺はサイクルを形成するため、スキップします。

すべての辺を処理した後、選択された辺が最小全域木（MST）を構成します（連結グラフの場合、それらはちょうどn - 1本になります）。