如何在具有奇数条边的两个节点之间查找路径

Question

我有一个有向无环图，我需要在起点和接收器之间找到一条边数为奇数的路径（该图可以包含多个接收器）。最后，我应该有一个 O（|V|+|E|）。

Answer 1

如果给定的顶点是 V，则复制它们，给出 U。 更改边以始终将 V 中的一个顶点连接到您的一个顶点，并将镜像对应项从 U 中开始，然后执行经典的广度优先搜索。

搜索将在 U 和 V 之间交替，并且由于起点在 U 中，接收器在 V 中，因此您只会找到具有奇数条边的路径。