给定有向图中的边，如果将每条边分配给一个节点，将分配的最大边数是多少？

Question

假设有一个有向图，有 5 个节点和 4 条边，格式为 (a, b)，其中有一条边从 a 到 b。

edges = [(1, 2), (4, 1), (4, 3), (3, 5)]

每条边都将被分配一个节点值，例如边 1（(1, 2) 边）可能会被分配节点 1 或 2。它将尝试分配第一个值 1，如果该编号已被分配，它将尝试分配给节点 2。如果 2 已被占用，则边 1 没有值。找到分配了一些值的最大边缘，以及选择分配哪些边缘的有效序列。

我的方法伪代码

function dfs (current node)
    if seen contains current node
        return
    for next node : graph[current node]
        if current node was not assigned to any edge before
            assign current node to the id of edge (current_node, next_node)
        if current node was assigned but next node was not
            assign next node to the id of edge (current_node, next_node)
        dfs(next_node)
seen = hashest
for num:all node
    if seen does not contain num and current node was not assigned to any edge
        dfs(num)

虽然这有时可行，但并不总能找到最大边数。有时，按顺序从节点 1 到 n 的 dfs 并不是最佳方法，或者至少这是我使用此代码发现的方法。是否有一个恒定的时间实现或者我必须从不同的节点开始搜索？例如，使用我的代码，假设我从边缘 4 (3, 5) 开始。根据我的算法，边 (3,5) 被分配给节点 3。然后，假设我从边 2 或 (4, 1) 开始。然后，边 2 被分配给节点 4，并且由于边 1 (1, 2) 是邻居，因此它被分配给节点 1。但是，这意味着边 (4,3) 未分配给任何节点。而且，实际上可以将节点分配给所有节点。

Answer 1

如果图是连通的（所有节点都可以从一个节点到达），那么可以分配一个数字的最大边数是min( E, N )，其中N是节点数，E是边数

算法是：

Copy graph, making all edges bidirectional
LOOP over edges in copy by using DFS
   IF src node unassigned, assign src to edge
   ELSE assign dst to edge

在您的示例中，假设首先查看 1-2 边，结果将为

1 - 2 < 1
1 - 4 < 4  ( 1 was assigned )
4 - 3 < 3
3 - 5 < 5

但是如果先看1-4

1 - 4 < 1
4 - 3 < 4
3 - 5 < 3
1 - 2 < 2 ( 1 was assigned )

顺便说一句，如果图没有连接，那么算法可以应用于每个组件。