algorithm - 从 n 个列表中选择 n 个唯一元素

Question

我一直在思考一个编程问题。如果我们有 n 个列表，我们想要输出 n 个不同元素(每个元素都来自一个不同列表)。我怀疑这可以通过某种回溯算法来解决，但我不知道如何正确实现它。

Answer 1

尽管您可以按照评论中的建议通过回溯来解决此问题，但更有效的解决方案是使用最大流算法。
将其建模为图形。一个 Source，一个 Sink，每个不同元素的节点和每个列表的节点。您将源连接到每个不同的元素。每个元素都连接到它所在的每个列表，列表连接到一个汇节点。每条边的容量为 1。
最大流是您可以从不同列表中选择的不同元素的最大数量。

https://en.wikipedia.org/wiki/Maximum_flow_problem
https://en.wikipedia.org/wiki/Edmonds%E2%80%93Karp_algorithm