How it works?

유니온 파인드(Union-find)는 parent 배열을 유지합니다. 각 정점은 자기 자신을 루트로 시작합니다. 두 가지 연산이 모든 것을 구동합니다:

• find(x): 루트(자기 자신을 부모로 갖는 정점)에 도달할 때까지 parent 링크를 따라갑니다. 두 정점이 같은 루트를 공유하면 서로 연결된 것입니다.
• union(a, b): 한 루트가 다른 루트를 가리키게 하여 두 집합을 합칩니다.

크루스칼 알고리즘 (Kruskal's Algorithm):

1. 가중치가 가장 작은 간선부터 큰 순서대로 처리합니다.
2. 각 간선에 대해 양 끝점의 루트를 find 합니다. 루트가 다르다면, 해당 간선은 두 개의 분리된 조각을 연결하는 것이므로, 이들을 union 하고 전체 가중치에 해당 간선의 가중치를 더합니다.
3. 루트가 같다면 해당 간선은 사이클을 형성하므로 건너뜁니다.

모든 간선을 처리한 후, 선택된 간선들이 MST를 형성합니다 (연결 그래프의 경우, 정확히 n - 1 개의 간선이 선택됩니다).