给定无向图，它有 M 条边和 N 个顶点，我们必须将每条边从 u-v 转换为 u->v 或 v->u，使得每个顶点的入度都是偶数。哪种方法或算法适合用时最少复杂性。
最佳答案
这是一种不同的方法 - 我认为您不想对 n=100,000 进行高斯消去法，所以我在网上搜索了相关问题。
如果图中有多个连通分量，您可以分别考虑它们，所以我们假设它只有一个。
在您的组件上构建一棵生成树，并将其中一个顶点标记为该树的根。随心所欲地修复不在生成树上的边的方向。从叶子开始，一次获取每个顶点，在处理该顶点之前处理该顶点的所有子节点。对于每个顶点，选择树边到其父节点的方向，使其入度均匀，并忽略对其父节点的影响。除了根之外的每个顶点都有一条边将它与其父节点相连，因此对于除根之外的每个顶点，您可以确保它的入度是偶数。
当你到达根节点时，你没有留下任何可以改变方向的边，所以你不能改变它的入度，这显然不是偶数就是奇数。如果是偶数，一切都很好——每个顶点的入度都是偶数。如果是奇数，则有一个顶点的入度为奇数，而所有其他顶点的入度为偶数，因此所有入度之和为奇数。但是所有入度的总和只是图中的边数，您无法更改。如果图中的边数为奇数，则总会有至少一个顶点的入度为奇数，无论如何都不可能解决这个问题。
关于algorithm - 将无向图转换为具有特定条件的有向图，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/53689396/