Pairing Friends Problem

Revision en1, by CipherText, 2020-05-04 20:51:47

There are $$$N$$$ persons. Each one of them has a friendship with zero or more of others. If $$$A$$$ is friend with $$$B$$$, then $$$B$$$ is also friend with $$$A$$$. Now they will have to form some teams, each containing two persons. Each member of a team must have a friendship with the other member of the team. The question is, what is the maximum number of teams that can be made?

For example,
$$$A$$$ is friend with $$$B$$$ and $$$D$$$.
$$$B$$$ is friend with $$$A$$$ and $$$C$$$.
$$$C$$$ is friend with $$$B$$$.
$$$D$$$ is friend with $$$A$$$.

Then, maximum two teams can be made: $$$(A,D)$$$ and $$$(B,C)$$$.

How to solve this if,

  • the upper bound of $$$N$$$ is $$$100$$$?
  • the upper bound of $$$N$$$ is $$$1000$$$?
  • the number of team members is any number in the range $$$[2,N]$$$?
Tags #problem discussion

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English CipherText 2020-05-04 20:51:47 761 Initial revision (published)