uva: 11060 – Beverages (Topological sort)

11060 - Beverages (Topological sort)

#include <stdio.h>
#include <iostream>
#include <map>
#include <vector>
#include <queue>
#include <string>
//#include <conio.h>

using namespace std;

typedef pair<string,int> namval;
typedef pair<int,string> valnam;
typedef vector vi;

struct compareval
{
	bool operator()(const int& a, const int& b)
	{
		return a > b;
	}
};

int main()
{
	int vertex, edge,tc=0;
	string str, start, end;

	while(scanf("%d", &vertex)==1)
	{
		map<string,int> name_value;
		map<int, string> value_name;

		for(int i=0; i < vertex; i++)
		{
			cin>>str;
			name_value.insert(namval(str, i));
			value_name.insert(valnam(i, str));
		}

		scanf("%d", &edge);
		vector adjList;
		adjList.assign(vertex,vi());

		vi indegree = vi(vertex);
		indegree.assign(vertex,0);

		for(int i=0; i < edge; i++)
		{
			cin>>start;
			cin>>end;

			int u = name_value.find(start)->second;
			int v = name_value.find(end)->second;

			adjList.at(u).push_back(v);
			indegree[v] +=1;
		}

		priority_queue<int, vector<int>, compareval> pq;

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

		vi order = vi();

		while(!pq.empty())
		{
			int u = pq.top(); pq.pop();
			order.push_back(u);

			for(int i=0; i < adjList[u].size(); i++)
			{
				 int v = adjList[u][i];
			 	 indegree[v]--;
				 if(indegree[v]==0 )
						 pq.push(v);
			}
		}

		printf("Case #%d: Dilbert should drink beverages in this order: %s",++tc, value_name[order[0]].data() );
		for(int i = 1; i < order.size(); i++)
		{
			printf(" %s",  value_name[order[i]].data());
		}
		printf(".\n\n");
	}
	//getch();
return 0;
}

//
/*

http://uva.onlinejudge.org/external/110/11060.html

Sample Input

3
vodka
wine
beer
2
wine vodka
beer wine

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

10
cachaca
rum
apple-juice
tequila
whiskey
wine
vodka
beer
martini
gin
11
beer whiskey
apple-juice gin
rum cachaca
vodka tequila
apple-juice martini
rum gin
wine whiskey
apple-juice beer
beer rum
wine vodka
beer tequila

Sample Output

Case #1: Dilbert should drink beverages in this order: beer wine vodka.

Case #2: Dilbert should drink beverages in this order: apple-juice beer wine rum cachaca.

Case #3: Dilbert should drink beverages in this order: apple-juice wine vodka beer rum cachaca tequila whiskey martini gin.

*/

Advertisements

About M Moniruzzaman
A passionate software engineer, have been developing applications on various platforms such as Android, iPhone, .Net (C#) technologies and web based ASP.NET, PHP, JavaScript, jQuery technologies for more than 10 years. Especially I have expertise on developing applications for Android and iPhone, as well as service oriented, client-server based applications where clients will be reside on Android/iPhone that communicate with WCF(.NET) service hosted on server. I have completed certification in Microsoft Certified Professional Developer (MCPD) on .Net 4 . I have completed my graduation in -- B.Sc. (Engineering) in Computer Science and Engineering, ShahJalal University of Science and Technology, Bangladesh. Thanks, M. Moniruzzaman (Zaman)

2 Responses to uva: 11060 – Beverages (Topological sort)

  1. Steven S says:

    Not to be negative or anything, but this code doesn’t compile with GCC

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: