当前位置: 动力学知识库 > 问答 > 编程问答 >

c++ - Efficient algorithm for finding max number of pairs

问题描述:

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.

分享给朋友:
您可能感兴趣的文章:
随机阅读: