UVa – 11060 – Beverages

Arunima Mandal

Problem Link: https://onlinejudge.org/external/110/11060.pdf

Note: This problem can be solved using basic topological sort but with a simple tweak to maintain the order required in the problem statement. I used a priority queue to maintain the ascending order of the nodes that have indegree 0.

Code:

#include <bits/stdc++.h>

using namespace std;


vector<int> topSort(int node, vector<int> &indeg, vector<vector<int> > &adj)
{
    vector<int> ans;
    priority_queue<int, vector<int>,  greater<int > > pq;

    for(int i=0; i<node; i++)
    {
        if(indeg[i]==0) pq.push(i);
    }

    while(!pq.empty())
    {
        int u=pq.top();
        pq.pop();
        ans.push_back(u);
        for(int j=0; j<adj[u].size(); j++)
        {
            int v=adj[u][j];
            indeg[v]--;
            if(indeg[v]==0) pq.push(v);
        }
    }
    return ans;
}


int main()
{
//    freopen("in.txt","r",stdin);
//    freopen("out.txt","w",stdout);

    int z=1;
    int node,edge;
    while(cin>>node)
    {
        unordered_map<string,int> mp1;
        unordered_map<int,string> mp2;
        int c=0;
        for(int i=0; i<node; i++)
        {
            string s;
            cin>>s;
            mp1[s]=c;
            mp2[c]=s;
            c++;
        }

        cin>>edge;
        vector<vector<int> > adj(node);
        vector<int> indeg(node,0);

        for(int i=0; i<edge; i++)
        {
            string from,to;
            cin>>from>>to;
            adj[mp1[from]].push_back(mp1[to]);
            indeg[mp1[to]]++;
        }

        vector<int> ans=topSort(node, indeg, adj);

        cout<<"Case #"<<z<<": Dilbert should drink beverages in this order:";

        for(int i=0; i<ans.size(); i++)
        {
            cout<<" "<<mp2[ans[i]];
        }
        cout<<"."<<endl<<endl;
        z++;
    }
    return 0;
}

Leave a comment