Problem 18 : Kruskal's Algorithm using c++

 

Problem 18 : Kruskal's Algorithm  using c++

by Ujjal Roy

 #include<bits/stdc++.h>

using namespace std;

#define ll long long int

const ll N=10000;

ll parent[N];

ll siz[N];

void make(ll node)

{

     parent[node]=node;

     siz[node]=1;

}

ll find_set(ll v)

{

     if(parent[v]==v)return v;

     return parent[v]=find_set(parent[v]);

}

void union_set(ll u,ll v)

{

    ll x,y;

    x=find_set(v);

    y=find_set(u);

    if(x!=y)

    {

        if(siz[x]<siz[y])swap(siz[x],siz[y]);

        parent[y]=x;

        siz[x]+=siz[y];

    }

}

int main()

{

    ll node,edge,i;

    cout<<"Enter number of node and edge : ";

    cin>>node>>edge;

    vector<vector<int>>adj;

    for(i=0;i<=node;i++)make(i);

    while(edge--)

    {

        cout<<"Enter U , V, W : ";

        ll u,v,w;

        cin>>u>>v>>w;

        adj.push_back({w,u,v});

    }

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

    ll sum;

    sum=0;

    for(i=0;i<adj.size();i++)

    {

         ll u,v,w;

         w=adj[i][0];

         u=adj[i][1];

         v=adj[i][2];

         if(find_set(u)!=find_set(v))

         {

             sum+=w;

             cout<<u<<" "<<v<<endl;

             union_set(u,v);

         }

    }

    cout<<"The sum is : "<<sum<<endl;

    return 0;

}