algorithm - 确定是否存在有效的数字排列

Question

我正在尝试创建一种算法，根据规则列表确定是否存在有效的数字排列。

我有 n 个节点和 n 个整数，每个节点都包含一个不能配对的整数列表，我的目标是确定它是否是可以将每个节点与一个整数配对。

目前，我最好的解决方案是尝试选择一个可以配对的数字和节点，将它们从列表中删除，然后递归调用我的函数。

在最坏的情况下，这可能会在阶乘时间内生成所有可能的排列。是否可以在不生成所有排列的情况下确定是否存在有效配对？

感谢您的帮助!

Answer 1

这个问题将简化为最大二分匹配，您可以使用 Ford - Fulkerson 算法在 O(nm) http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm 中解决它.

我们的想法是，您可以创建一个顶点为 n 个整数和 n 个节点的图，并且如果您可以使用该整数表示该节点，则从该节点到该整数的有向边将存在。当应用上述算法时，该图可以分为两组。