问题描述:

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.