Category Minimum Spanning Tree

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

UVa – 11631 – Dark Roads

Arunima Mandal Leave a comment

Problem Link: https://onlinejudge.org/external/116/11631.pdf

Note: This problem is a simple implementation of the Minimum Spanning Tree(MST) with a very simple tweak. I applied Prim’s algorithm here, Krushkal’s algorithm can also be used.

Code:

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


using namespace std;

int Prims(vector<vector<pair<int, int> > > &edges, int node)
{
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > >pq;
    int vis[200005]= {0};
    int ans=0;
    int nodes_added=0;
    pq.push({0,0});
    while(nodes_added<node)
    {
        int from=pq.top().second;
        int cost=pq.top().first;
        pq.pop();
        if(!vis[from])
        {
            nodes_added++;
            vis[from]=1; //added to MST
            ans+=cost;
            for(int i=0; i<edges[from].size(); i++)
            {
                pair<int,int> to=edges[from][i];
                pq.push(to);
            }
        }
    }
    return ans;
}

int main()
{
    int node, edge;
    while(cin>>node>>edge)
    {
        if(node==0 && edge==0) break;
        vector<vector<pair<int, int> > > edges(node);
        int total_cost = 0;
        for(int i=0; i<edge; i++) //Building adjacency graph
        {
            int x,y,cost;
            cin>>x>>y>>cost;
            edges[x].push_back({cost, y});
            edges[y].push_back({cost, x});
            total_cost+=cost;
        }
        int ans=Prims(edges, node);
        cout<<total_cost-ans<<endl;
    }
    return 0;
}

Prim’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. Build an adjacency matrix
  2. Select a random node to start with and push that to the priority queue(ascending ordered value.)
  3. Do this until the number of nodes added to the MST list is less than the total number of nodes n:
    • For each top() of the priority queue, check whether the node has already been considered for the MST list, if not then do:
      • Add that node to the MST list (marked visited)
      • Add the cost(surely it will be the lowest value possible in the priority queue) of the edge to the answer
      • Push all the adjacent nodes of that node to the priority queue to determine which node to add next.

Time Complexity:

O(ElogV) where E is the number of edges and V is the number of nodes.

Code:

#include <bits/stdc++.h>

using namespace std;

int Prims(vector<vector<pair<int, int> > > &edges, int n)
{
    priority_queue<pair<int,int>, vector<pair<int,int> >, greater<pair<int,int> > >pq;
    int vis[1003]= {0};
    int ans=0;
    int nodes_added=0;
    pq.push({0,0});
    while(nodes_added<n)
    {
        int cost=pq.top().first;
        int node=pq.top().second;
        pq.pop();
        if(!vis[node])
        {
            nodes_added++;
            vis[node]=1; //added to MST
            ans+=cost;
            for(int i=0; i<edges[node].size(); i++)
            {
                pq.push(edges[node][i]);
            }
        }
    }
    return ans;
}

int main()
{
    int n,m;
    cout<<"Enter the no. of nodes in the graph: ";
    cin>>n;
    cout<<"Enter the no. of edges: ";
    cin>>m;
    vector<vector<pair<int, int> > > edges(n);
    cout<<"Enter the and their corresponding cost (node node cost):"<<endl;
    for(int i=0; i<m; i++) //Building adjacency graph
    {
        int x,y,cost;
        cin>>x>>y>>cost;
        edges[x].push_back({cost, y});
        edges[y].push_back({cost, x});
    }
    int ans=Prims(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

*/

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

*/