Read an undirected weighted graph and build a minimum spanning forest with Kruskal's algorithm and a union–find structure (union by size or rank, and path compression).
Input
n m // vertices 0 .. n-1, number of edges
u1 v1 w1 // m lines: undirected edge with integer weight w
...
Self-loops and parallel edges may appear.
Rules
- Sort the edges by weight. Edges with equal weight keep their input order (use a stable sort such as
List.sort). - Scan the edges in that order and accept an edge only if its endpoints are in different sets.
Output — each accepted edge, in the order accepted, written exactly as in the input as u - v : w; then the total weight and the number of connected components (1 for a connected graph). For
7 11
0 1 4
0 2 3
1 2 5
1 3 2
2 3 7
2 4 8
3 4 6
3 5 9
4 5 1
4 6 5
5 6 4
the output is
4 - 5 : 1
1 - 3 : 2
0 - 2 : 3
0 - 1 : 4
5 - 6 : 4
3 - 4 : 6
Total weight: 20
Components: 1