图形算法，给边分配合适的方向
Graphic algorithm, assign proper direction to edge
有一个无向图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?
对于任何只有一条边连接的顶点，如果你能解决这个难题，你仍然可以在确定连接到该顶点的唯一边具有指向该顶点的方向后解决它。
所以我会在每个顶点上使用计数器来跟踪连接到该顶点的边的数量，并重复设置一端在一个顶点上而没有其他附加边的边的方向，然后删除这些边和从图中删除它们的顶点（或将它们标记为已删除）并继续。
如果此过程以空图终止，则没有循环，您已解决问题。
如果它以一个或多个循环结束，其中每个顶点都附有两条边，则为一条边选择方向并沿着它绕循环选择你遇到的每条边的唯一可能方向。如果有多个循环，您将不得不多次执行此操作以设置所有剩余边的方向。
如果这终止于一个附有两条以上边的顶点，并且每个顶点附有一条以上边，那么你有比循环更复杂的东西，并且无法分配路径和方向，因此每个顶点都有最多一个。
有一个无向图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?
对于任何只有一条边连接的顶点，如果你能解决这个难题，你仍然可以在确定连接到该顶点的唯一边具有指向该顶点的方向后解决它。
所以我会在每个顶点上使用计数器来跟踪连接到该顶点的边的数量，并重复设置一端在一个顶点上而没有其他附加边的边的方向，然后删除这些边和从图中删除它们的顶点（或将它们标记为已删除）并继续。
如果此过程以空图终止，则没有循环，您已解决问题。
如果它以一个或多个循环结束，其中每个顶点都附有两条边，则为一条边选择方向并沿着它绕循环选择你遇到的每条边的唯一可能方向。如果有多个循环，您将不得不多次执行此操作以设置所有剩余边的方向。
如果这终止于一个附有两条以上边的顶点，并且每个顶点附有一条以上边，那么你有比循环更复杂的东西，并且无法分配路径和方向，因此每个顶点都有最多一个。