We are given N pairs. Each pair contains two numbers. We have to find maximum number K such that if we take any combination of J (1<=J<=K) pairs from the given N pairs, we have at least J different numbers in all those selected J pairs. We can have more than one pair same.
已知N对。每一对都包含两个数字。我们必须找到最大K，这样如果我们从给定的N对中取任意的J (1<=J<=K)对，我们至少有J个不同的数字在所有选择的J对中。我们可以有多于一对相同的。
For example, consider the pairs (1,2) (1,2) (1,2) (7,8) (9,10) For this case K = 2, because for K > 2, if we select three pairs of (1,2), we have only two different numbers i.e 1 and 2.
例如，在K = 2的情况下，考虑对(1,2)(1,2)(1,2)(7,8)(9,10)因为对于K > 2，如果我们选择三对(1,2)，我们只有两个不同的i。e 1和2。
Checking for each possible combination starting from one will take a very large amount of time. What would be an efficient algorithm for solving the problem?
检查每个可能的组合，从一个开始将花费大量的时间。什么是解决问题的有效算法?
4 个解决方案
#1
0
Create a graph with one vertex for each number and one edge for each pair.
创建一个图，每个顶点为一个顶点，每一对为一条边。
If this graph is a chain or a tree, we have the number of "numbers", equal to number of "pairs" plus one, After removing any number of edges from this graph, we never get less vertexes than edges.
如果这个图是一个链或者树，我们有“数字”的数量，等于“对”的数量加上1，在从这个图中删除任意数量的边之后，我们得到的顶点永远比边少。
Now add a single cycle to this chain/tree. There is equal number of vertexes and edges. After removing any number of edges from this graph, again we never get less vertexes than edges.
现在在这个链/树中添加一个循环。顶点和边的数量相等。在从这个图中删除任意数量的边之后，我们得到的顶点永远不会比边少。
Now add any number of disconnected components, each should not contain more than one cycle. Once again, we never get less vertexes than edges after removing any number of edges.
现在添加任意数量的断开连接的组件，每个组件不应该包含多个循环。再一次，除去任意数量的边，我们永远不会得到比边更少的顶点。
Now add a second cycle to any of disconnected components. After removing all other components. at last we have more edges than vertexes (more pairs than numbers).
现在向任何断开连接的组件添加第二个循环。在删除所有其他组件之后。最后我们得到了比顶点更多的边(比数字多对)。
All this leads to the conclusion that K+1 is exactly the number of edges in the smallest possible subgraph, consisting of two cycles and, possibly, a chain, connecting these cycles.
所有这些得出的结论是，K+1恰好是最小的可能子图的边数，它包含两个周期，也可能是一个链，连接着这些周期。
Algorithm:
For each connected component, find the shortest cycle going through every node with Floyd-Warshall algorithm.
对于每个连通分量，使用Floyd-Warshall算法找到每个节点的最短周期。
Then for each non-overlapping pair of cycles (in single component), use Dijkstra’s algorithm, starting from any node with at least 3 edges in one cycle, to find shortest path to other cycle; and compute a sum of lengths of both cycles and a shortest path, connecting them. For each overlapping pair of cycles, just compute the number of their edges.
然后，对于每一对不重叠的周期(在单个组件中)，使用Dijkstra算法，从一个周期中至少有3条边的任何节点开始，找到到另一个周期的最短路径;计算两个周期和最短路径的长度之和，并将它们连接起来。对于每一对重叠的循环，只需计算它们的边数。
Now find the minimum length of all these subgraphs. And subtract 1.
现在求所有这些子图的最小长度。减去1。
The above algorithm computes K if there is at least one double-cycle component in the graph. If there are no such components, K = N.
如果图中至少有一个双周期分量，上述算法计算K。如果没有这样的分量，K = N。
#2
0
Seems related to MinCut/MaxFlow. Here is a try to reduce it to MinCut/MaxFlow:
似乎相关MinCut / MaxFlow。这里有一个尝试将它减少到MinCut/MaxFlow:
- Produce one vertex for each number
- Produce one vertex for each pair
- Produce an edge from number i to a pair if the number is present in the pair, weight 1
- Produce a source node and connect it to all numbers, weight 1 for each connection
- Produce a sink node and connect it to all numbers, weight 1 for each connection
Running MaxFlow on this should give you the number K, since any set of three pairs which only contains two numbers in total, will be "blocked" by the constrains on the outgoing edges from the number.
在这上面运行MaxFlow应该会给你数字K，因为任何一组三对只包含两个数字，将会被从数字的输出边的约束“阻塞”。
I am not sure whether this is the fastest solution. There might also be a matroid hidden in there somewhere, I think. In that case there is a greedy approach. But I cannot find a proof for the matroid properties of the sets you are constructing.
我不确定这是否是最快的解决方案。我想那里可能也藏着一个马特罗。在这种情况下，存在一种贪婪的方法。但是我找不到证明你正在构造的集合的matroid属性的证明。
#3
0
I made some progress on it, but not yet an efficient solution. However it may point the way.
我在这方面取得了一些进展，但还不是一个有效的解决方案。然而，它可能会指明道路。
Make a graph whose points are pairs, and connect any pair of points if they share a number. Then for any subgraph, the number of numbers in it is the number of vertices minus the number of edges. Therefore your problem is the same as locating the smallest subgraph (if any) that has more edges than vertices.
制作一个点为对的图，如果它们共享一个数字，那么将它们连接起来。对于任何子图，数字的个数是顶点数减去边数。因此，您的问题等同于定位具有比顶点更多边的最小子图(如果有的话)。
A minimal subgraph that has the same number of edges and vertices is a cycle. Therefore the graphs we're looking for are either 2 cycles that share one or more vertices, or else 2 cycles which are connected by a path. There are no other minimal types possible.
具有相同数目的边和顶点的最小子图是一个循环。因此我们要找的图要么是共享一个或多个顶点的两个周期，要么是由路径连接的两个周期。不可能有其他最小类型。
You can locate and enumerate cycles fairly easily with a breadth-first search. There may be a lot of them, but this is doable. Armed with that you can look for subgraphs of these subtypes. (Enumerate minimal cycles, look for either pairs that share points, or which are connected.) But that isn't guaranteed to be polynomial. I suspect it will be something where on average it is pretty good, but the worst case is very bad. However that may be more efficient than what you're doing now.
你可以很容易地找到并列举出一个面包优先搜索的周期。可能有很多，但这是可行的。有了它，您可以查找这些子类型的子图。(枚举最小循环，查找共享点或连接的对。)但这不能保证是多项式。我猜想这将是一个平均来说相当不错的事情，但最坏的情况是非常糟糕的。然而，这可能比你现在做的更有效。
I keep on thinking that some kind of breadth-first search can find these in polynomial time, but I keep failing to see exactly how to do it.
我一直在想某种广度优先的搜索可以在多项式时间中找到它们，但我一直没能找到具体的方法。
#4
0
This is equivalent to finding the chord that chords the smallest cycle in the graph. A very naive algorithm would be:
这等价于找到弦是图中最小周期的弦。一种非常幼稚的算法是:
Check if removal of an edge results in a cycle containing the vertices corresponding to the edge. If yes, then note down the length of the smallest cycle.
检查删除一条边是否会导致包含与该边对应的顶点的循环。如果是，那么记下最小周期的长度。
#1
0
Create a graph with one vertex for each number and one edge for each pair.
创建一个图，每个顶点为一个顶点，每一对为一条边。
If this graph is a chain or a tree, we have the number of "numbers", equal to number of "pairs" plus one, After removing any number of edges from this graph, we never get less vertexes than edges.
如果这个图是一个链或者树，我们有“数字”的数量，等于“对”的数量加上1，在从这个图中删除任意数量的边之后，我们得到的顶点永远比边少。
Now add a single cycle to this chain/tree. There is equal number of vertexes and edges. After removing any number of edges from this graph, again we never get less vertexes than edges.
现在在这个链/树中添加一个循环。顶点和边的数量相等。在从这个图中删除任意数量的边之后，我们得到的顶点永远不会比边少。
Now add any number of disconnected components, each should not contain more than one cycle. Once again, we never get less vertexes than edges after removing any number of edges.
现在添加任意数量的断开连接的组件，每个组件不应该包含多个循环。再一次，除去任意数量的边，我们永远不会得到比边更少的顶点。
Now add a second cycle to any of disconnected components. After removing all other components. at last we have more edges than vertexes (more pairs than numbers).
现在向任何断开连接的组件添加第二个循环。在删除所有其他组件之后。最后我们得到了比顶点更多的边(比数字多对)。
All this leads to the conclusion that K+1 is exactly the number of edges in the smallest possible subgraph, consisting of two cycles and, possibly, a chain, connecting these cycles.
所有这些得出的结论是，K+1恰好是最小的可能子图的边数，它包含两个周期，也可能是一个链，连接着这些周期。
Algorithm:
For each connected component, find the shortest cycle going through every node with Floyd-Warshall algorithm.
对于每个连通分量，使用Floyd-Warshall算法找到每个节点的最短周期。
Then for each non-overlapping pair of cycles (in single component), use Dijkstra’s algorithm, starting from any node with at least 3 edges in one cycle, to find shortest path to other cycle; and compute a sum of lengths of both cycles and a shortest path, connecting them. For each overlapping pair of cycles, just compute the number of their edges.
然后，对于每一对不重叠的周期(在单个组件中)，使用Dijkstra算法，从一个周期中至少有3条边的任何节点开始，找到到另一个周期的最短路径;计算两个周期和最短路径的长度之和，并将它们连接起来。对于每一对重叠的循环，只需计算它们的边数。
Now find the minimum length of all these subgraphs. And subtract 1.
现在求所有这些子图的最小长度。减去1。
The above algorithm computes K if there is at least one double-cycle component in the graph. If there are no such components, K = N.
如果图中至少有一个双周期分量，上述算法计算K。如果没有这样的分量，K = N。
#2
0
Seems related to MinCut/MaxFlow. Here is a try to reduce it to MinCut/MaxFlow:
似乎相关MinCut / MaxFlow。这里有一个尝试将它减少到MinCut/MaxFlow:
- Produce one vertex for each number
- Produce one vertex for each pair
- Produce an edge from number i to a pair if the number is present in the pair, weight 1
- Produce a source node and connect it to all numbers, weight 1 for each connection
- Produce a sink node and connect it to all numbers, weight 1 for each connection
Running MaxFlow on this should give you the number K, since any set of three pairs which only contains two numbers in total, will be "blocked" by the constrains on the outgoing edges from the number.
在这上面运行MaxFlow应该会给你数字K，因为任何一组三对只包含两个数字，将会被从数字的输出边的约束“阻塞”。
I am not sure whether this is the fastest solution. There might also be a matroid hidden in there somewhere, I think. In that case there is a greedy approach. But I cannot find a proof for the matroid properties of the sets you are constructing.
我不确定这是否是最快的解决方案。我想那里可能也藏着一个马特罗。在这种情况下，存在一种贪婪的方法。但是我找不到证明你正在构造的集合的matroid属性的证明。
#3
0
I made some progress on it, but not yet an efficient solution. However it may point the way.
我在这方面取得了一些进展，但还不是一个有效的解决方案。然而，它可能会指明道路。
Make a graph whose points are pairs, and connect any pair of points if they share a number. Then for any subgraph, the number of numbers in it is the number of vertices minus the number of edges. Therefore your problem is the same as locating the smallest subgraph (if any) that has more edges than vertices.
制作一个点为对的图，如果它们共享一个数字，那么将它们连接起来。对于任何子图，数字的个数是顶点数减去边数。因此，您的问题等同于定位具有比顶点更多边的最小子图(如果有的话)。
A minimal subgraph that has the same number of edges and vertices is a cycle. Therefore the graphs we're looking for are either 2 cycles that share one or more vertices, or else 2 cycles which are connected by a path. There are no other minimal types possible.
具有相同数目的边和顶点的最小子图是一个循环。因此我们要找的图要么是共享一个或多个顶点的两个周期，要么是由路径连接的两个周期。不可能有其他最小类型。
You can locate and enumerate cycles fairly easily with a breadth-first search. There may be a lot of them, but this is doable. Armed with that you can look for subgraphs of these subtypes. (Enumerate minimal cycles, look for either pairs that share points, or which are connected.) But that isn't guaranteed to be polynomial. I suspect it will be something where on average it is pretty good, but the worst case is very bad. However that may be more efficient than what you're doing now.
你可以很容易地找到并列举出一个面包优先搜索的周期。可能有很多，但这是可行的。有了它，您可以查找这些子类型的子图。(枚举最小循环，查找共享点或连接的对。)但这不能保证是多项式。我猜想这将是一个平均来说相当不错的事情，但最坏的情况是非常糟糕的。然而，这可能比你现在做的更有效。
I keep on thinking that some kind of breadth-first search can find these in polynomial time, but I keep failing to see exactly how to do it.
我一直在想某种广度优先的搜索可以在多项式时间中找到它们，但我一直没能找到具体的方法。
#4
0
This is equivalent to finding the chord that chords the smallest cycle in the graph. A very naive algorithm would be:
这等价于找到弦是图中最小周期的弦。一种非常幼稚的算法是:
Check if removal of an edge results in a cycle containing the vertices corresponding to the edge. If yes, then note down the length of the smallest cycle.
检查删除一条边是否会导致包含与该边对应的顶点的循环。如果是，那么记下最小周期的长度。