cpp mst

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

using namespace std;

// Structure to represent an edge in the graph
struct Edge {
    int source, destination, weight;
};

// Function to compare edges based on their weights for sorting
bool compareEdges(const Edge& a, const Edge& b) {
    return a.weight < b.weight;
}

// Function to find the parent of a vertex in a disjoint set
int findParent(int vertex, vector<int>& parent) {
    if (parent[vertex] == -1)
        return vertex;
    return findParent(parent[vertex], parent);
}

// Function to perform union of two sets
void unionSets(int x, int y, vector<int>& parent) {
    int rootX = findParent(x, parent);
    int rootY = findParent(y, parent);
    parent[rootX] = rootY;
}

// Function to perform Kruskal's algorithm for finding the Minimum Spanning Tree
vector<Edge> kruskalMST(vector<Edge>& edges, int numVertices) {
    // Sort the edges based on their weights
    sort(edges.begin(), edges.end(), compareEdges);

    vector<int> parent(numVertices, -1);
    vector<Edge> resultMST;

    for (const Edge& edge : edges) {
        int rootSource = findParent(edge.source, parent);
        int rootDest = findParent(edge.destination, parent);

        // Check if including this edge forms a cycle
        if (rootSource != rootDest) {
            resultMST.push_back(edge);
            unionSets(rootSource, rootDest, parent);
        }
    }

    return resultMST;
}

int main() {
    // Number of vertices and edges in the graph
    int numVertices, numEdges;
    cin >> numVertices >> numEdges;

    // Read the edges of the graph
    vector<Edge> edges(numEdges);
    for (int i = 0; i < numEdges; ++i) {
        cin >> edges[i].source >> edges[i].destination >> edges[i].weight;
    }

    // Find and print the Minimum Spanning Tree using Kruskal's algorithm
    vector<Edge> resultMST = kruskalMST(edges, numVertices);
    for (const Edge& edge : resultMST) {
        cout << edge.source << " " << edge.destination << " " << edge.weight << endl;
    }

    return 0;
}