How it works?

O Union-find mantém um array parent. Cada vértice começa como sua própria raiz. Duas operações conduzem tudo:

• find(x): siga os links parent até alcançar uma raiz (um vértice que é seu próprio pai). Dois vértices estão conectados quando compartilham uma raiz.
• union(a, b): aponte uma raiz para a outra, mesclando os dois conjuntos.

Algoritmo de Kruskal:

1. Processe as arestas do menor peso para o maior.
2. Para cada aresta, use find para encontrar as raízes de suas extremidades. Se elas forem diferentes, a aresta une duas partes separadas: use union nelas e adicione seu peso ao total.
3. Se as raízes forem as mesmas, a aresta formaria um ciclo, então ignore-a.

Após processar cada aresta, as arestas escolhidas formam a MST (para um grafo conectado, exatamente n - 1 delas).