Kruskal's algorithm|C++|MST

PHOTO EMBED

Sun Jun 23 2024 19:01:32 GMT+0000 (Coordinated Universal Time)

Saved by @utp #c++ 

#include <iostream>
#include <vector>
#include <algorithm>

class DisjointSet {
public:
    DisjointSet(int n) {
        rank.resize(n + 1, 0);
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        for (int i = 0; i <= n; ++i) {
            parent[i] = i;
        }
    }

    int find_upar(int node) {
        if (node == parent[node]) {
            return node;
        }
        return parent[node] = find_upar(parent[node]);
    }

    void union_by_rank(int u, int v) {
        int ulp_u = find_upar(u);
        int ulp_v = find_upar(v);
        if (ulp_u == ulp_v) {
            return;
        }
        if (rank[ulp_u] < rank[ulp_v]) {
            parent[ulp_u] = ulp_v;
        } else if (rank[ulp_v] < rank[ulp_u]) {
            parent[ulp_v] = ulp_u;
        } else {
            parent[ulp_v] = ulp_u;
            rank[ulp_u]++;
        }
    }

    void union_by_size(int u, int v) {
        int ulp_u = find_upar(u);
        int ulp_v = find_upar(v);
        if (ulp_u == ulp_v) {
            return;
        }
        if (size[ulp_u] < size[ulp_v]) {
            parent[ulp_u] = ulp_v;
            size[ulp_v] += size[ulp_u];
        } else {
            parent[ulp_v] = ulp_u;
            size[ulp_u] += size[ulp_v];
        }
    }

private:
    std::vector<int> rank;
    std::vector<int> parent;
    std::vector<int> size;
};

class Solution {
public:
    int spanningTree(int V, std::vector<std::vector<std::pair<int, int>>>& adj) {
        std::vector<std::tuple<int, int, int>> edges;
        for (int i = 0; i < V; ++i) {
            for (auto& it : adj[i]) {
                int adjNode = it.first;
                int wt = it.second;
                int node = i;
                edges.push_back(std::make_tuple(wt, node, adjNode));
            }
        }

        DisjointSet ds(V);
        std::sort(edges.begin(), edges.end());

        int mstWt = 0;
        for (auto& edge : edges) {
            int wt = std::get<0>(edge);
            int u = std::get<1>(edge);
            int v = std::get<2>(edge);
            if (ds.find_upar(u) != ds.find_upar(v)) {
                mstWt += wt;
                ds.union_by_size(u, v);
            }
        }

        return mstWt;
    }
};

int main() {
    int V = 5;
    std::vector<std::vector<std::pair<int, int>>> adj(V);

    std::vector<std::vector<int>> edges = {
        {0, 1, 2}, {0, 2, 1}, {1, 2, 1}, {2, 3, 2}, {3, 4, 1}, {4, 2, 2}
    };

    for (auto& it : edges) {
        int u = it[0], v = it[1], wt = it[2];
        adj[u].emplace_back(v, wt);
        adj[v].emplace_back(u, wt);
    }

    Solution obj;
    int mstWt = obj.spanningTree(V, adj);
    std::cout << "The sum of all the edge weights: " << mstWt << std::endl;

    return 0;
}
content_copyCOPY