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.

I think a standard breadth first search is enough for this problem :) — Pham Trung, Apr 14 '15 at 02:22
I thought so. But for that I have to find the root. But that is what the requirement is. right? — Novice123, Apr 14 '15 at 02:26
are all the edges listed belong to the path? Or they can contain unrelated edge? If not, a simple trick can overcome this as Anonymous has pointed out. — Pham Trung, Apr 14 '15 at 02:54

Paul Hankin · Accepted Answer · 2015-04-14T02:48:32.390

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

Finding the correct path in O(n) time

1 Answers1