问题描述:

This question already has an answer here:

  • Choosing mutually exclusive pairs efficiently

    4 answers

网友答案:

This problem can be solved in polynomial time complexity using Bloossom algorithm: http://en.wikipedia.org/wiki/Blossom_algorithm

Form a graph where each number is node and connect each pair with edge. Run the above mentioned algorithm on this graph to find solution.

网友答案:

So your valid pairs could be represented as a graph, and then the maximum number of pairs is a maximum matching in that graph.

Note that you can have multiple solutions. For valid pairs [(0,1),(1,2),(2,3),(3,4)] both [(0, 1), (2, 3)] and [(1, 2), (3, 4)] are solutions.

相关阅读:
Top