# 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(orbigraph) is agraphwhoseverticescan be divided into twodisjointandindependent setsUandVsuch that everyedgeconnects a vertex inUto one inV.

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-lengthcycles.

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:

- Start with an arbitrary vertex,
`u`

. Randomly assign Team 1 to it. - For every assigned vertex of the graph, iterate over its neighbors
- If a neighbor
`v`

of`u`

is already assigned, and has opposite team number, keep it. - If
`v`

has the same team number, we have found an odd-length cycle. Return`False`

- Otherwise, place
`v`

in the opposite team of`u`

.

In this post, we are going to provide three implementations of this iterative strategy

- Using
*Breadth First Search (BFS)* - Using
*Depth First Search (DFS)*implemented recursively - Using
*Depth First Search (DFS)*implemented iteratively

# Preliminaries:

Let’s define some common typedefs, structs and helpers we are going to we are going to use. Since we either return a pair or False from the function, this is a good opportunity to use `std::variant`

defined in *C++17*. Note that we are going to use `bool`

types `{true, false}`

to internally represent the two teams.

# Breadth First Search (BFS):

BFS algorithm simply maintains a queue of `Assignment`

structs.

- At every iteration, it pops a student-team pair from the front of the queue.
- For every neighbor of the popped student, it tries to assign the opposite team, and simply returns false if the assignment ends up in conflict.

# Depth First Search (DFS) (recursive):

Here are main differences between a BFS and DFS from implementation standpoint:

- We need an additional map
`discovered`

to update when we first visit the student_id. - We always assign a color to a vertex before

# Depth First Search (DFS) (iterative)

The iterative version of DFS is perhaps the hardest to implement! In order to convert the recursive version above to an iterative one, we have to maintain two stacks

- A stack of
`Assignment`

structs which keep track of team assignments - A stack to keep track of the current offset in the neighbor list of the current student.

# Complexity:

The complexities of all three algorithms are same as those of standard DFS/BFS algorithms. In particular, we iterate over every edge and vertex of the graph exactly once, and perform constant amount of work for every iteration. As a result, the complexity is `O(V + E)`

where `V`

is the number of students, and `E`

is the number of enemy relations.

# Testing:

Here are a few test cases to try. As always, use `UnorderedElementsAre`

matcher of `GUnit`

tests as your friend 🙂 :

- No students
- A single pair of students, both enemies of each other
- All empty enemy lists
- Complex enemy lists (with or without odd length cycles

*Originally published at **https://cppcodingzen.com** on September 13, 2020.*