You're given pairs of people who don't get along. Return true if everyone can be
split into exactly two teams so that no pair of rivals ends up on the same team.
(This is a bipartite-graph check on the conflict graph.)
tolerantTeams(graph)
Input format: conflict pairs as a,b (undirected).
a,b a,c // → true (a alone; b,c together)
a,b b,c c,a // → false (three mutual rivals can't split into 2 teams)
"Split everyone into two teams so no rivals share a team" asks: can this rivalry graph be 2-colored? Assign each person a team so every rivalry edge connects two differently-colored nodes. The problem reduces to: is the conflict graph bipartite?
With many rivalries, you can't eyeball an assignment — you need a systematic way to build a valid coloring or prove none exists. Once one person's team is fixed, every rival is forced onto the other team, every rival of those forced back, and so on — no freedom of choice within a connected group.
This forced propagation is exactly a graph traversal. Start at an unassigned person, team 0. Their rivals get team 1, those rivals' rivals get team 0, alternating outward until everyone reachable is assigned — one component fully colored.
The critical check: encountering a rival already assigned. If their team matches the current person's, that's a contradiction — return false. If opposite, consistent, move on.
Each connected component colors independently (no rivalry path means no constraint between them), so restart the traversal from any unvisited person to handle each component. Making it through every component without a same-team rivalry means a valid split exists — constructively built.
A graph is bipartite exactly when it has no odd-length cycle. Alternating colors around an even cycle closes up cleanly; an odd cycle forces the start and end of the loop onto the same color despite being adjacent — the exact contradiction the traversal detects.
def tolerant_teams(graph):
team = {}
for start in graph:
if start in team:
continue
team[start] = 0
queue = [start]
while queue:
node = queue.pop(0)
for rival in graph.get(node, []):
if rival in team:
if team[rival] == team[node]:
return False
else:
team[rival] = 1 - team[node]
queue.append(rival)
return True
Sign in to join the discussion.
No comments yet. Be the first to ask a question.
Press Run to execute your code, or Submit to test and complete this problem.