question archive Assume that you need to divide 71 participants into two teams (say, team 0 and team 1)
Assume that you need to divide 71 participants into two teams (say, team 0 and team 1)
Subject:Computer SciencePrice: Bought3
Assume that you need to divide 71 participants into two teams (say, team 0 and team 1). Let N be the set of all participants (so IN | = n), and each participant Z G N can make requests of the form "I want to be in the same team as X" or "I do not want to be in the same team as Y", where X ,Y E N, Z 75 X, and Z 75 Y. Let the total number of such requests be Is. The resulting teams do not have to be equal size. In an extreme case we might put all the participants into the same team. Design an ef?cient algorithm to divide the participants into two teams while satisfying all the requests, assuming that is possible. If it is impossible to satisfy the requests, then return "Not possible". [Hintz convert the problem input into an appropriate graph, ?nd the connected components of this graph. Then construct an appropriate "meta-graph" consisting of the connected components and solve the problem on this "meta-graph" .]
