algorithm - 图形算法，给边分配合适的方向

Question

有一个无向图 G = (V, E)，我如何为每条边分配一个方向，以便每个顶点在 O(V+ E) 时间？应该有2个条件:

Situation 1. G has no cycle
What should I use? BFS or DFS, and how?

Situation 2. G has at most 1 cycle
If there is a cycle how could we choose the direction of 2 edges that point to the same vertex?

Answer 1

对于任何只有一条边连接到它的顶点，如果你能解决这个难题，你仍然可以在确定连接到该顶点的唯一边具有指向该顶点的方向后解决它。

所以我会在每个顶点上使用计数器来跟踪连接到该顶点的边的数量，并重复设置一端位于一个顶点上而没有其他附加边的边的方向，然后删除这些边及其顶点从图中删除(或将它们标记为已删除)并继续。

如果此过程以空图终止，则没有循环，您已解决问题。

如果它终止于一个或多个循环，其中每个顶点都附有两条边，则为一条边选择方向，然后沿着它绕循环，为您遇到的每条边选择唯一可能的方向。如果有多个循环，您将不得不多次执行此操作以设置所有剩余边的方向。

如果这终止于一个附有两条以上边的顶点，并且每个顶点附有一条以上边，那么你有比循环更复杂的东西，并且无法分配路径和方向，因此每个顶点都有 -最多一个学位。