Twitter: Dodgeball Team and Bipartite Graph

Problem:

A teacher must divide a class of students into two teams to play dodgeball. Unfortunately, not all the kids get along, and several refuse to be put on the same team as that of their enemies.

Given an adjacency list of students and their enemies, write an algorithm that finds a satisfactory pair of teams, or returns False if none exists.

For example, given the following enemy graph you should return the teams {0, 1, 4, 5} and {2, 3}.

students = { 
  0: [3], 
  1: [2], 
  2: [1, 4], 
  3: [0, 4, 5], 
  4: [2, 3], 
  5: [3] 
}

On the other hand, given the input below, you should return False.

students = { 
  0: [3], 
  1: [2], 
  2: [1, 3, 4], 
  3: [0, 2, 4, 5], 
  4: [2, 3], 5: [3] 
}

Solution:

Like many programming interview questions, this question is a standard application of a known graph algorithm, called The Bipartite Graph.

According to Wikipedia,

bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V such that every edge connects a vertex in U to one in V.

Moreover, a standard theorem regarding bipartite graphs gives an immediate algorithm for bipartite-partitioning the graph, and also for finding whether such a partition exists

a bipartite graph is a graph that does not contain any odd-length cycles.

Note that the example 1 in the problem statement has no odd-length cycle, while example 2 has a single odd-length cycle: 2->3->4.

Here is one scheme for finding an odd-length cycle:

1. Start with an arbitrary vertex, u. Randomly assign Team 1 to it.
2. For every assigned vertex of the graph, iterate over its neighbors
3. If a neighbor v of u is already assigned, and has opposite team number, keep it.
4. If v has the same team number, we have found an odd-length cycle. Return False
5. Otherwise, place v in the opposite team of u.