How it works?

Система непересекающихся множеств (Union-find) хранит массив parent. Каждая вершина изначально является своим собственным корнем. Все строится на двух операциях:

• find(x): следуйте по ссылкам parent, пока не достигнете корня (вершины, которая является родителем самой себе). Две вершины считаются связанными, если у них общий корень.
• union(a, b): направьте один корень на другой, объединяя два множества.

Алгоритм Краскала:

1. Обрабатывайте ребра в порядке возрастания их веса (от меньшего к большему).
2. Для каждого ребра выполните find, чтобы найти корни его конечных точек. Если они различаются, ребро соединяет два отдельных компонента: выполните union для них и добавьте вес ребра к общей сумме.
3. Если корни совпадают, ребро образует цикл, поэтому пропустите его.

После обработки всех ребер выбранные ребра образуют минимальное остовное дерево (MST) (для связного графа их будет ровно n - 1).