Can Everyone Be Split Into Two Teams
Solve this ProblemThere are n people, and some pairs of people clash. The clashes are given as an adjacency list of an undirected graph. Decide whether all people can be divided into two teams so that no two people who clash are on the same team.
This is the question whether the graph is bipartite. Colouring the graph with two colours, spreading from each person to the people they clash with, either succeeds or exposes a conflict.
Test Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ n ≤ 10 people numbered 0 … n-1; graph[u] lists every person who dislikes or clashes with u (adjacency-list form of an undirected graph) - ◆
If v is in graph[u] then u is in graph[v]; nobody clashes with themselves, and there are no repeated entries - ◆
The graph may be disconnected (several separate groups) - ◆
Return true if everyone can be placed in one of two teams so that no two people who clash are on the same team, otherwise false
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Try Every Way of Splitting Into Two Teams
BruteEach person is on team 0 or team 1, so there are 2ⁿ ways to assign teams; write an assignment as an n-bit number (bit u is the team of person u). For every assignment check all clashes: if two people who clash have the same bit, the assignment is bad. If any assignment passes, the answer is true; if all 2ⁿ fail, false. Fine for tiny n, hopeless for large ones.
O(2ⁿ · (n + E))O(1)1class Solution {
2 public boolean canSplitInTwoTeams(int[][] graph) {
3 int n = graph.length;
4 for (int mask = 0; mask < (1 << n); mask++) {
5 boolean ok = true;
6 for (int u = 0; u < n; u++) {
7 for (int v : graph[u]) {
8 if (((mask >> u) & 1) == ((mask >> v) & 1)) ok = false;
9 }
10 }
11 if (ok) return true;
12 }
13 return false;
14 }
15}Optimal — Colour the Graph With Breadth-First Search
OptimalOnce a person's team is fixed, all of their clashes are forced onto the other team. So: pick an uncoloured person, put them on team 0 and search outwards; each newly reached person gets the opposite team of the person they were reached from. If we ever meet a neighbour that already has the SAME team as the current person, two clashing people are forced together, so it is impossible. Repeat from each uncoloured person to cover separate groups. Every person and clash is looked at a constant number of times: O(n + E).
O(n + E)O(n)1class Solution {
2 public boolean canSplitInTwoTeams(int[][] graph) {
3 int n = graph.length;
4 int[] team = new int[n];
5 Arrays.fill(team, -1);
6 for (int start = 0; start < n; start++) {
7 if (team[start] != -1) continue;
8 team[start] = 0;
9 Deque<Integer> queue = new ArrayDeque<>();
10 queue.add(start);
11 while (!queue.isEmpty()) {
12 int u = queue.poll();
13 for (int v : graph[u]) {
14 if (team[v] == -1) {
15 team[v] = 1 - team[u];
16 queue.add(v);
17 } else if (team[v] == team[u]) {
18 return false;
19 }
20 }
21 }
22 }
23 return true;
24 }
25}