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

Question

考虑有一条从源到目的地的路径，但是这条路径被打乱了。

例如：

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

假设没有循环，我们能否在O(n)时间内从混乱的路径中恢复原始路径。

- Novice123

---

我认为标准的广度优先搜索就足够解决这个问题了 :) - Pham Trung

我也是这么想的。但为此我必须找到根源。但这就是要求，对吧？ - Novice123

所有列出的边都属于路径吗？还是它们可能包含无关的边？如果不是，就像Anonymous指出的那样，有一个简单的技巧可以克服这个问题。 - Pham Trung

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

- Paul Hankin