Category Krushkal’s algorithm

UVa – 11747 – Heavy Cycle Edges

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/117/11747.pdf

Note: This problem is a variation of the Minimum Spanning Tree(MST) and it gives a deeper understanding of Krushkal’s algorithm.

We know that we need to run the Union-Find algorithm in Krushkal’s and we run that up to (node – 2) edges. Because we just need to check – starting from any node, whether we can reach any node or not. For example: if there are 3 nodes in a graph – 1,2,3. Then having edges between 1-2-3 would be enough and will form an MST. No direct edge between 1-3 is required.

But to solve this problem, we’ll need to check up to (node – 1) edges, to check for a cycle. That’s the main trick!

Code:

#include <iostream>
#include <iomanip>
#include <fstream>
#include <algorithm>
#include <new>
#include <map>
#include <unordered_map>
#include <queue>
#include <vector>
#include <set>
#include <algorithm>
#include <climits>

using namespace std;

int Find(int x, vector<int> &root)
{
    if(root[x]==x) return x;
    return root[x]=Find(root[x], root);
}

void Union(int x, int y, vector<int> &root, vector<int> &ranking)
{
    int rootX=Find(x, root);
    int rootY=Find(y, root);
    if(rootX!=rootY)
    {
        if(ranking[rootX]>=ranking[rootY]) root[rootY]=rootX;
        else if(ranking[rootY]>=ranking[rootX]) root[rootX]=rootY;
        else
        {
            root[rootY]=rootX;
            ranking[rootX]++;
        }
    }
}

vector<int> Krushkals(vector<pair<int, pair<int, int> > > &edges, int node)
{
    sort(edges.begin(), edges.end());
    vector<int> root(node);
    vector<int> ranking(node);
    for(int i=0; i<node; i++)
    {
        root[i]=i;
        ranking[i]=1;
    }
    int edge_added=0;
    vector<int> ans;
    int maxi=INT_MIN;
    for(int i=0; i<edges.size() && edge_added<node; i++)
    {
        int x=edges[i].second.first;
        int y=edges[i].second.second;
        int cost=edges[i].first;
        if(Find(x, root)!=Find(y, root)) //if no cycle exists
        {
            Union(x,y,root, ranking);
            edge_added++;
            maxi=max(maxi, cost);
        }
        else
        {
            
            maxi=max(maxi, cost);
            ans.push_back(maxi);
            maxi=INT_MIN;
        }
    }
    return ans;

}

int main()
{
    int node,edge;
    while(cin>>node>>edge)
    {
        if(node==0 && edge==0) break;
        vector<pair<int, pair<int, int> > > edges;

        for(int i=0; i<edge; i++)
        {
            int x,y,cost;
            cin>>x>>y>>cost;
            edges.push_back({cost, {x, y}});
        }
        vector<int> ans=Krushkals(edges, node);
        if(ans.size()==0) cout<<"forest"<<endl;
        else
        {
            for(int i=0; i<ans.size()-1; i++) cout<<ans[i]<<" ";
            cout<<ans[ans.size()-1]<<endl;
        }
    }
    return 0;
}

Krushkal’s algorithm – Minimum Spanning Tree (MST)

Arunima Mandal Leave a comment

Note:

It’s a greedy approach. Basically, there are 3 steps in Krushkal’s algorithm.

  1. Sort the edges according to their cost in ascending order.
  2. Traverse through the sorted edges list upto n-1 length
    • a.If the edge creates a loop(use Find or Union of Union-Find to check the loop), do not consider it.
    • b. else add it to the MST list by using Union and add the cost of the edge to the answer.

Time Complexity:

O(ElogE) where E is the number of edges.

Code:

#include <bits/stdc++.h>

using namespace std;

int Find(int x, vector<int> &root)
{
    if(root[x]==x) return x;
    return root[x]=Find(root[x], root);
}

void Union(int x, int y, vector<int> &root, vector<int> &rankk)
{
    int rootX=Find(x, root);
    int rootY=Find(y, root);
    if(rootX!=rootY)
    {
        if(rankk[rootX]>=rankk[rootY]) root[rootY]=rootX;
        else if(rankk[rootY]>=rankk[rootX]) root[rootX]=rootY;
        else
        {
            root[rootY]=rootX;
            rankk[rootX]++;
        }
    }
}

int Krushkals(vector<vector<int>> &edges, int n)
{
    sort(edges.begin(), edges.end());
    vector<int> root(n+1);
    vector<int> rankk(n+1);
    for(int i=0; i<n; i++)
    {
        root[i]=i;
        rankk[i]=1;
    }
    int ans=0, groups=0;
    for(int i=0; i<edges.size() && groups<n-1; i++)
    {
        int x=edges[i][1];
        int y=edges[i][2];
        int cost=edges[i][0];
        if(Find(x, root)!=Find(y, root)) //if no cycle exists
        {
            Union(x,y,root, rankk);
            ans+=cost;
            groups++;
        }
    }
    return ans;

}

int main()
{
    int n,m;
    vector<vector<int> > edges;
    cout<<"Enter the no. of nodes in the graph: ";
    cin>>n;
    cout<<"Enter the no. of edges: ";
    cin>>m;
    cout<<"Enter the and their corresponding cost (node node cost):"<<endl;
    for(int i=0; i<m; i++)
    {
        int x,y,cost;
        cin>>x>>y>>cost;
        edges.push_back({cost, x, y});
    }
    int ans=Krushkals(edges, n);
    cout<<"The minimum cost for traversing all the nodes once: "<<ans<<endl;
    return 0;
}
/*
Sample input:
5
7
0 1 1
0 2 2
0 3 3
1 2 2
2 3 3
3 4 4
4 0 5

Sample Output:
10

Note: Minimum spanning tree formed by nodes 0-1-2-3-4

*/