Splitting into two teams
Decide whether people with conflicts can be split into two teams so that nobody shares a team with someone they clash with. About 15 minutes.
Forced choices
You are organising a game. Some pairs of people don't get along, and you want two teams where no team contains a pair that clashes. Can it be done?
Start with anyone and put them in team 0. Everyone they clash with must go in team 1. Everyone those people clash with must go back in team 0, and so on. The choices are forced, so you simply spread them out like a ripple, handing each new person the opposite team of the person who reached them.
colour = [-1] * n colour[start] = 0 colour[nxt] = 1 - colour[node]
Start with person 0 and put them in team 0.
Spot the clash
Keep going until every person has a team. The only thing that can go wrong is when you look at a person you clash with, they already have a team, and it is the same as yours. Then both of you would be forced onto the same team, so no split exists.
People who clash with nobody in your group start their own ripple. Start a new one from every person without a team, so separate groups are each checked.
if colour[nxt] == colour[node]:
return FalseThree people all clash with each other (a triangle). Can they be split into two teams?
- ANo. Person 1 goes in team 0, so 2 and 3 are forced into team 1, where they clash
- BYes, two in one team and one in the other
- CIt depends who goes first
Show the answer
No. Person 1 goes in team 0, so 2 and 3 are forced into team 1, where they clash. Any loop with an odd number of people forces two clashing people onto the same team.
Two teams
There are n people, numbered 0 to n − 1. clashes[i] = [a, b] means person a and person b do not get along. Return true if the people can be split into two teams so that no two people who clash are on the same team, and false otherwise. A team may be empty.
n = 5, clashes = [[0, 1], [0, 3], [1, 2], [2, 3], [3, 4]] → true
1 ≤ n ≤ 100,000 · 0 ≤ clashes ≤ 200,000