UVa 11060

From Algorithmist
Jump to navigation Jump to search

Problem ID[edit]

Problem Number: UVA 11060; Problem Name: Beverages; Problem Link: http://uva.onlinejudge.org/index.php?option=onlinejudge&page=show_problem&problem=2001


Summary[edit]

Sorting a list of beverages according to the relative order of their alcohol content.


Explanation[edit]

First a list the names of N beverages will be given (B1, B2, ... , BN). Then there will follow M relationship between those beverages in the following format: Bi Bj. It means that beverage Bj has more alcohol than beverage Bi, and while drinking, Bi should come before Bj.

The relationships are transitive, which means, if Ba should be taken before Bb and Bb should be taken before Bc, then Ba should be taken before Bc. In the case there is no relation between two beverages Bx and By, if Bx comes before By in list B1, B2, ..., BN, then Bx should be taken before By.

The task is to generate a list of the beverages so that they can be taken in the order of their alcohol content, i.e. from the lowest alcohol level to the highest alcohol level.


Gotchas[edit]

1. Notice the sentence in the problem statement: In the case there is no relation between two beverages Dilbert should start drinking the one that appears first in the input. This sentence implies that there is only one valid solution to the problem, unlike many other topological sorting problems.

2. Format the output exactly according to the sample output. Notice the period.

Notes[edit]

The problem is similar to other graph theory problems which gives additional condition for choosing a certain topologically sorted list among all the possible topologically sorted lists.

Implementations[edit]

Category: Graph Theory, Topological sorting. Implement Kahn's algorithm.

First, store all the names of the beverages, as they appear on the input, in a list A. It might be better to map the names to an integer and also map the integer back to the name of the beverage. Then create a directed graph G denoting the dependency between the beverages, where the nodes in the graph represent the names of the beverages. Keep track of the in degree of all the nodes in the graph.

iterate all the nodes (beverages) in the order given in list A. Take the first node u in list A whose in degree is zero and insert the node to a list T which represents the topologically sorted beverages. Decrease the in degree of all the node v by one, where the ordered pair (u,v) represents an edge of the graph G. Discard node u from list A. Again start from the beginning of A and take the first node out whose in degree is zero and insert into the list T. Keep doing this until all the nodes are discarded from A and inserted into T.

The list T now gives the order of the beverages in the desired order.

Optimizations[edit]

1. Use adjacency list instead of adjacency matrix to store the graph.

2. Use priority queue to topsort; which in this case, reduces the time complexity to O(n^2);

Input[edit]

3
A
B
C
1
A C

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

Output[edit]

Case #1: Dilbert should drink beverages in this order: A B C.

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

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

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

References[edit]

http://en.wikipedia.org/wiki/Topological_sorting

Categories here, use the form [[Category: Category Name]], see Categories for a list