kruskal's MST algorithm

kruskal.cpp

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct DisjointSet {
    vector<int> parent;
    vector<int> size;
};

struct Edge {
    int u, v, w; // Vertex u, Vertex v, Weight w
};

struct edges_lower_weight {
    bool operator()(const Edge& a, const Edge& b) 
    {
        return a.w < b.w;
    }
};

static DisjointSet ds;
static vector<Edge> edges;

int FindSet(int n)
{
    int root, j, k;
    j = n;
    while (ds.parent[j] != j) {
        j = ds.parent[j];
    }
    root = j;
    j = n;
    while (ds.parent[j] != j) {
        k = ds.parent[j];
        ds.parent[j] = root;
        j = k;
    }
    return root;
}

void Merge(int a, int b)
{
    // a = FindSet(a);
    // b = FindSet(b);

    if (ds.size[a] < ds.size[b]) {
        ds.parent[a] = b;
        ds.size[b] += ds.size[a]; 
    }
    else {
        ds.parent[b] = a;
        ds.size[a] += ds.size[b]; 
    }
}

int main()
{
    int n, m; // num Vertices, num Edges
    while (cin >> n >> m) {
        ds.parent = vector<int>(n+1);
        ds.size = vector<int>(n+1);
        edges = vector<Edge>(m);

        for (int i = 0; i <= n; ++i) {
            ds.parent[i] = i;
            ds.size[i] = 1;
        }

        for (int i = 0; i < m; ++i) {
            cin >> edges[i].u >> edges[i].v >> edges[i].w;
        }

        sort(edges.begin(), edges.end(), edges_lower_weight());

        int total_weight = 0;
        int mst_edge_count = 0;

        for (const Edge& e : edges) {
            int u_set = FindSet(e.u);
            int v_set = FindSet(e.v);
            if (u_set != v_set) {
                Merge(u_set, v_set);
                total_weight += e.w;
                ++mst_edge_count;
                if (mst_edge_count == n - 1) break; // MST completed, other edges will be discarted
            }
        }

        cout << total_weight << endl;
    }
}