algorithm - 寻找最大数量 k 使得对于 k 对的所有组合，我们在每个组合中有 k 个不同的元素

Question

我们有 N 对。每对包含两个数字。我们必须找到最大数 K，这样如果我们从给定的 N 对中取 J (1<=J<=K) 对的任意组合，在所有这些选定的 J 对中我们至少有 J 个不同的数。我们可以有不止一对相同的。

例如，考虑对(1,2)(1,2)(1,2)(7,8)(9,10)对于这种情况 K = 2，因为对于 K > 2，如果我们选择三对 (1,2)，我们只有两个不同的数字，即 1 和 2。

从一个开始检查每个可能的组合将花费大量时间。解决该问题的有效算法是什么？

Answer 1

创建一个图，每个数字一个顶点，每对一个边。

如果这个图是一条链或一棵树，我们有“数字”的数量，等于“对”的数量加一，从这个图中删除任意数量的边后，我们得到的顶点永远不会少于边。

现在向这个链/树添加一个循环。顶点和边的数量相等。从该图中删除任意数量的边后，我们得到的顶点永远不会少于边。

现在添加任意数量的断开组件，每个组件不应包含超过一个循环。再一次，在删除任意数量的边后，我们得到的顶点永远不会少于边。

现在向任何断开连接的组件添加第二个循环。删除所有其他组件后。最后我们的边比顶点多(对数比数字多)。

所有这些都得出结论，K+1 恰好是最小可能子图中的边数，由两个循环和可能的链组成，连接这些循环。

算法:

对于每个连接的组件，使用 Floyd-Warshall 算法找到经过每个节点的最短循环。

然后对于每个不重叠的循环对(在单个组件中)，使用 Dijkstra 算法，从一个循环中至少有 3 条边的任何节点开始，找到到另一个循环的最短路径；并计算两个循环的长度之和和连接它们的最短路径。对于每个重叠的循环对，只需计算它们的边数。

现在找出所有这些子图的最小长度。并减去 1。

如果图中至少有一个双循环分量，则上述算法会计算 K。如果没有这样的组件，K = N。