PROBLEM LINK:
Editorialist: Kaustubh Khavnekar
DIFFICULTY:
Medium
PREREQUISITES:
Map data structure
PROBLEM:
The individual connections between devices A and B in a Rube Goldberg machine are given. Your task is to find the overall path of the Rube Goldberg machine.
QUICK EXPLANATION:
Express connections from A to B and to B from A as two different maps. Find device which is in forward map but not reverse map and construct path starting from that device.
EXPLANATION:
Each connection consists of two parts, A and B. The problem can be solved in linear time using a map data structure. Note that the starting device will not appear as the second part in any connection, since no other device has a connection to that device. We can find this device by first making two maps, from A to B (forward map) and then from B to A (reverse map). Then we iterate through all forward mappings, and find a device which has a forward mapping but no reverse mapping. This is the starting device. Starting from this device, we can traverse all edges in order using the forward mappings.
SOLUTION:
Solution can be found here.