UVa – 11747 – Heavy Cycle Edges

Arunima Mandal

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;
}

Leave a comment