kruskal's

#include <bits/stdc++.h>

using namespace std;

// Structure to represent an edge

struct Edge {

int src, dest, weight;

};

// Comparator to sort edges by weight

bool compare(Edge a, Edge b) {

return a.weight < b.weight;

}

// Disjoint Set Union (Union-Find)

class DSU {

vector<int> parent, rank;

public:

DSU(int n) {

parent.resize(n);

rank.resize(n, 0);

for (int i = 0; i < n; i++) parent[i] = i;

}

int find(int u) {

if (u != parent[u])

parent[u] = find(parent[u]); // Path compression

return parent[u];

}

bool unite(int u, int v) {

int pu = find(u);

int pv = find(v);

if (pu == pv) return false; // Already connected

// Union by rank

if (rank[pu] < rank[pv])

parent[pu] = pv;

else if (rank[pu] > rank[pv])

parent[pv] = pu;

else {

parent[pv] = pu;

rank[pu]++;

}

return true;

}

};

// Function to construct MST using Kruskal's Algorithm

void kruskalMST(int V, vector<Edge> &edges) {

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

DSU dsu(V);

vector<Edge> result;

for (auto &e : edges) {

if (dsu.unite(e.src, e.dest)) {

result.push_back(e);

}

}

// Print result

cout << "Edge \tWeight\n";

for (auto &e : result)

cout << e.src << " - " << e.dest << " \t" << e.weight << "\n";

}

// Driver Code

int main() {

int V = 5;

vector<Edge> edges = {

{0, 1, 2}, {0, 3, 6}, {1, 2, 3},

{1, 3, 8}, {1, 4, 5}, {2, 4, 7}, {3, 4, 9}

};

kruskalMST(V, edges);

return 0;

}