Code : Kruskal's Algorithm

#include <iostream>
#include<bits/stdc++.h>
using namespace std;

// Union by Size
class disjoint_set{

    vector<int> size,parent;

    public:

    // constructor
    disjoint_set(int n){
        size.resize(n+1,1);
        parent.resize(n+1);

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

    int find_ultimate_parent(int node){

        // base case
        if(parent[node]==node){
            return node;
        }

        // applying recursion for path compression
        return parent[node] = find_ultimate_parent(parent[node]);

    }

    void union_by_size(int u,int v){

        int ulp_u = find_ultimate_parent(u);
        int ulp_v = find_ultimate_parent(v);

        // already belong to same component
        if(parent[ulp_u] == parent[ulp_v]){return;}   

        // connect the smaller component to larger component
        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];
        }

        return;
    }

};
int main() {
    
    int n,m;
    cin>>n;
    cin>>m;

    priority_queue<pair<int,pair<int,int>>,vector<pair<int,pair<int,int>>>,greater<pair<int,pair<int,int>>>>pq;

    int times = m;
    while(times--){

        int u,v,wt;
        cin>>u>>v>>wt;

        pq.push({wt,{u,v}});
        
    }

    vector<pair<int,pair<int,int>>> ans;
    disjoint_set ds = disjoint_set(n);

    while(!pq.empty()){

        int u = pq.top().second.first;
        int v = pq.top().second.second;
        int wt = pq.top().first;

        pq.pop();


        // if already belong to same component than can cause loop
        if(ds.find_ultimate_parent(u)==ds.find_ultimate_parent(v)){
            continue;
        }

        ans.push_back({wt,{u,v}});
        ds.union_by_size(u,v);

    }

    for(auto it : ans){

        int wt = it.first;
        int u = it.second.first;
        int v = it.second.second;

        int v1,v2;

        if(u<v){
            v1 = u;
            v2 = v;
        }
        else{
            v1 = v;
            v2 = u;
        }

        cout<<v1<<" "<<v2<<" "<<wt<<endl;
    }

    return 0;
}

#include <bits/stdc++.h>

using namespace std;

class disjointset{

vector<int> size,parent;

public:

disjointset(int n){

size.resize(n+1);

parent.resize(n+1);

for(int i=0;i<n;i++){

parent[i] = i;

size[i] = 1;

}

}

int findUparent(int node){

if(node == parent[node]){

return node;

}

return parent[node] = findUparent(parent[node]);

}

int unionbysize(int u,int v){

int up_u = findUparent(u);

int up_v = findUparent(v);

if(size[up_u] < size[up_v]){

parent[up_u] = up_v;

size[up_v] += size[up_u];

}

else{

parent[up_v] = up_u;

size[up_u] += size[up_v];

}

}

};

int main() {

int V,E;

cin>>V>>E;

vector<pair<int,pair<int,int>>> edge;

for(int i=0;i<E;i++){

int u,v,wt;

cin>>u>>v>>wt;

if(u<V || v<V){

edge.push_back({wt,{u,v}});

}

}

sort(edge.begin(),edge.end());

disjointset ds(V);

vector<pair<pair<int,int>,int>> ans;

for(auto it:edge){

int wt = it.first;

int u = it.second.first;

int v = it.second.second;

if(ds.findUparent(u) != ds.findUparent(v)){

ds.unionbysize(u,v);

if(u<v){

// cout<<u<<v<<wt<<endl;

ans.push_back({{u,v},wt});

}

else{

// cout<<v<<u<<wt<<endl;

ans.push_back({{v,u},wt});

}

}

}

for(int it=ans.size()-1;it>=0;it--){

cout<<ans[it].first.first<<" ";

cout<<ans[it].first.second<<" ";

cout<<ans[it].second;

cout<<endl;

}

return 0;

}

In TEST CASE 3 →

i am getting 

2 3 2

1 3 2

0 3 2

but the answer is

2 3 2

1 3 2

0 1 2

both have SAME weight therefore the mst is still true for my output too.

we can have multiple mst for a graph.

Hey everyone, creating this thread to discuss the interview problem - Code : Kruskal's Algorithm.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Code : Kruskal's Algorithm