Algorithm to find pairs Task: There are N persons. Some of the persons were meet before. I need to find pairs of persons, that were not meet before.
Example: 4 persons - A, B, C, D.
A and B were meet before.
Good solutions: (A + C, B + D) OR (A + D, B + C).
Bad solution: (C + D) because it is forrbidden to create pair (A + B).
What algorithm can help to resolve this task?
It seems that you are looking for a maximum matching in a graph where vertices represent people and an (undirected) edge $(u,v)$ means that $u$ and $v$ have not met before.
This problem can be solved in time $O(n^{1/2} \cdot m) = O(n^\frac{5}{3})$, where $n$ is the number of people and $m$ is the number of pairs of people that have not yet met.