UVA 11060 Solution --Beverages

Explanation:

It is not simple Topological sort problem.
I tried to explain how I resolved it.
Read following explanation.

Input:

 ---------------------------------------------------------------------
3
vodka
wine
beer
2
wine vodka
beer wine
same sequence of given input(vodka, wine, beer)
vodka-->
wine--->
beer--->

Given relation:
wine vodka
drink wine before vodka. So, vodka depends on wine.
So, vodka--->wine,

beer wine
drink beer before wine. So, wine depends on beer.
So, wine--->beer.

Now, the structure is:
vodka--->wine,
wine--->beer
beer--->

Now, check top to bottom which has zero dependency.
beer has zero dependency. First drink beer.
Now, delete beer from structure because he already drunk the beer.
And erase beer from all elements which depends on beer.
1st output is beer.
Then, structure looks like below.
vodka--->wine.
wine--->

Again check top to bottom which has zero dependency. Now, find wine.
Then he drink wine.
Now, delete wine from structure because he already drunk the wine.
And erase wine from all elements which depends on wine.
2nd output is wine.
Then, structure looks like below.
vodka--->

Again check top to bottom which has zero dependency. Now, find vodka.
Then he drink vodka.
Now, delete vodka from structure because he already drunk the vodka.
And erase vodka from all elements which depends on vodka.
3rd output is vodka.
Then, structure looks like below.
The structure is empty. end of loop.

So, the output is beer wine vodka.

----------------------------------------------------------------------


5
wine
beer
rum
apple-juice
cachaca
6
beer cachaca
apple-juice beer
apple-juice rum
beer rum
beer wine
wine cachaca

Then builds the structure which looks like below:

wine---------->beer,
beer---------->apple-juice,
rum----------->apple-juice, beer,
apple-juice--->
cachaca------->beer,wine

Now check which has zero dependency.
Found apple-juice which has zero dependency.
delete apple-juice from structure.
And erase apple-juice from all elements which depends on apple-juice.
1st output is apple-juice.
Then, structure looks like below.
wine---------->beer,
beer---------->
rum----------->beer,
cachaca------->beer,wine

Now check which has zero dependency.
Found beer which has zero dependency.
delete beer from structure.
And erase beer from all elements which depends on beer.
2nd output is beer.
Then, structure looks like below.
wine---------->
rum----------->
cachaca------->wine

Again check.
Now found wine. 3rd output is wine.
Done same work which did previous drink.
Then, structure looks like below.
rum----------->
cachaca------->

Again check.
Now found rum. 4th output is rum.
Done same work which did previous drink.
Then, structure looks like below.
cachaca------->

Again check.
Now found cachaca. 5th output is cachaca.
Done same work which did previous drink.
Then, structure looks like below.

The structure is empty. end of loop.

So, the output is apple-juice beer wine rum cachaca

-----------------------------------------------------------------

 Code:

/*
uva 11060 solution
uva id: shoaib05
Accepted Time: 0.003 
*/

#include<iostream>
#include<string>
#include<map>
#include<set>
#include<algorithm>
#include<vector>

using namespace std;
typedef set<int> setint;

map<string,int> mymap;
map<int,string> mymap2;
map<int,setint> result;
vector<int> vec;
map<int,setint>::iterator rit;
setint::iterator sit;

int main()
{
freopen("file.txt","r",stdin);
string str,str2;
int i,x,y,test,m,n;
test=1;
while(cin>>n)
{
mymap.clear();
mymap2.clear();
vec.clear();
for(i=1;i<=n;i++)
{
cin>>str;
mymap[str]=i;
mymap2[i]=str;
result[i].insert(0);
}
cin>>m;
for(i=0;i<m;i++)
{
cin>>str>>str2;
x=mymap[str2];
y=mymap[str];
result[x].insert(y);
}
while(result.size()!=0)
{
for(rit=result.begin();rit!=result.end();rit++)
{
if(rit->second.size()==1)
{
x=rit->first;
result.erase(x);
break;
}
}
vec.push_back(x);
for(rit=result.begin();rit!=result.end();rit++)
{
if(rit->second.size()>1)
{
sit=rit->second.find(x);
if(sit!=rit->second.end())
{
rit->second.erase(x);
}
}
}
}
cout<<"Case #"<<test++<<": Dilbert should drink beverages in this order:";
for(i=0;i<n;i++)
{
cout<<" "<<mymap2[vec[i]];
}
cout<<"."<<endl<<endl;
}
    return 0;
}