在 O(n) 时间内找到正确的路径

Question

考虑有一条从源到目的地的路径，但路径是混乱的。

例如

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

假设没有环路，给定Jumbled路径，我们能否在O(n)时间内找回原来的路径。

Answer 1

路径的起点是一对元素中出现的第一个元素，而不是第二个元素。在路径中构建从开始到下一个节点的映射，并遍历它。

三个步骤中的每一步都是 O(n)，给出了 O(n) 的整体解决方案。

这是 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)

示例运行：

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

在 O(n) 时间内找到正确的路径

Finding the correct path in O(n) time

c

python

java

algorithm

time-complexity