Solution UVA: 11060 - Beverages

 

Problem	Verdict	Lang	Time	Best	Rank	Submit Time
| discuss11060 - Beverages	Accepted	C++11	0.020	0.000	3082	40 secs ago

Suggest:

This problem has two important points to note:

<1> The Topological Sort algorithm using DFS is not feasible in this problem. (maybe)

Despite trying for a day, I couldn't find a solution using this approach. Some hints from uDebug also suggest that DFS cannot be used to find the topological order, and instead, Kahn's algorithm should be used.

<2> The input can have duplicate values, which can lead to incorrect results. 

Example:

4

c

w

ca

v

5

c v

c ca

c ca

v ca

v w

#include <bits/stdc++.h>

#define X first

#define Y second

using namespace std;

int n, m;

unordered_map<string, bool> g;

unordered_map<string, int> indegree;

vector<pair<int, string>> vertex;

priority_queue<pair<int, string>> listSource;

int main(){

    ios::sync_with_stdio(false); cin.tie(nullptr);

    int cnt= 0;

    while (cin >> n) {  vertex.clear(); g.clear(); indegree.clear();

       

        string s;

        for(int i=0; i<n; i++)

            cin >> s, vertex.push_back({n-i,s});

           

        cin >> m;

        while(m--){

            string u, v;

            cin >> u >> v;

            if (g[u+"+"+v] == true) continue;

            g[u+"+"+v]= true;

            indegree[v]++;

        }

   

        for (auto p: vertex)

            if (!indegree[p.Y]) listSource.push({p.X, p.Y});

       

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

       

        string topo="";

        while (!listSource.empty()) {

            string u = listSource.top().Y;  listSource.pop();

           

            topo+=u+" ";

           

            for (auto p : vertex) {

                auto v= p.Y;

                if (g[u+"+"+v]){

                    indegree[v]--;

                    if (!indegree[v]) listSource.push({p.X, p.Y});

                }

            }

        }

        topo.erase(topo.size()-1);

        cout<<topo<<".\n\n";

    }

}