Finding the correct path in O(n) time

Question

Consider there is a path from source to destination but is jumbled up.

For example

A B      E F
B C      A B
C D  ->  D E
D E      C D
E F      B C

Assuming there are no cycles, Given the Jumbled path can we get back the original path in O(n) time.

Answer 1

The start of the path is the element that appears as the first thing in a pair, but not the second. Build a map from start to next node in the path, and iterate through it.

Each of the three steps is O(n), giving an O(n) overall solution.

Here's some example code in Python 2.7:

import sys

follow = dict(line.strip().split() for line in sys.stdin)
x = set(follow).difference(follow.itervalues()).pop()
while x:
    print x
    x = follow.get(x)

Example run:

$ echo -e "E F\nA B\nD E\nC D\nB C" | python follow.py 
A
B
C
D
E
F