PROBLEM LINK
DIFFICULTY
SIMPLE
PREREQUISITES
Ad Hoc, Graph Theory, Associative Arrays
PROBLEM
You are given N nodes and N-1 directed edges. You have to arrange the N-1 edges such that they form a linear path from the first node (the one with no in-edges) to the last node (the one with no out-edges).
You also have to find the sum of cost of the edges, which can be done trivially.
EXPLANATION
Let us assume we are given an array of edges E.
- E[i].from is the starting node of the edge i.
- E[i].to is the ending node of the edge i.
- E[i].cost is the cost of the edge i.
Let F be the set of cities that are mentioned as from in any of the edges.
- F must be a container that allows for efficient insertion and lookup.
- An example would be the hash_set container in C++, or the HashSet container in JAVA.
- Node that you can also use the set container in C++, but set is based on RB-Trees and allows insertion or lookup in O(log N) time, where N is the number of keys stored.
Let T be the set of cities that are mentioned as to in any of the edges.
- T must also be as efficient as F.
F - T (the subtraction of the set T from F) will contain only one city, say C. This city is the starting city for our resultant path.
Observe the following pseudo-code to calculate F - T.
for each f in F // O(|F|)
if T.contains(f) // O(1)
F.delete(f) // O(1)
Let, Fr be an associative array.
- Associative Arrays can also be deemed as Hash Tables.
- They allow O(1) storage and lookup of (key, value) pairs.
- An example would be the hash_map container in C++, or the HashMap container in JAVA.
- Node that you can also use the map container in C++, but map is based on RB-Trees and allows insertion or lookup in O(log N) time, where N is the number of (key,value) stored.
Observe the following snippet of pseudo-code for building Fr
for i = 1 to N-1 // O(N)
Fr[ E[i].from ] = i // O(1)
As you can see,
- Fr maps a city name to an integer.
- To be precise, Fr maps the city which appers as the from city in edge i to i.
Now, we have sufficient data structures to efficiently construct the path from the city C.
Observe the following snippet of pseudo-code
while Fr.contains(C) // O(|Fr|)
e = E[ Fr[C] ] // O(1)
print e.from, e.to, e.cost // O(1)
C = e.to // O(1)
The above snippet will efficiently spit the required path.
This problem can also be solved using Topological Sorting. Since the graph for this problem contains N nodes and N-1 edges, the complexity of the Depth First Search would remain O(N).
SETTERS SOLUTION
Can be found here.
TESTERS SOLUTION
Can be found here.
