Grouping and sorting algorithm help

Question

Lets say I have a million people objects that, when evaluated using

person1.Matches(person2);

return true or false.

I want to put them into groups. These groups are made by any one person being a match with any other person in the group. So any person from one group will NOT be a match with any person from another group. Any person in one group will be a match for at least one person in the same group. For example if an individual is asexual it will form a group of one person. A FAITHFUL married couple will form a group of two. A husband and his wife and his mistress and the mistresses husband would form a group of 4.

Just so you know, this algorithm would be used to analyze geometries.

Answer 1

This problem looks exactly like the connected components problem. Your graph vertexes being the persons, and the graph edges being the "Matches" relation. It could be solved by either BFS or DFS (read about it in the link from wikipedia, it gives a good explanation about it).