Split Into Two Teams

Medium

A department has n employees numbered 0 to n - 1. The list conflicts[u] holds the people employee u does not get along with. Conflicts are mutual: if v is in conflicts[u], then u is in conflicts[v]. Nobody clashes with themselves and the lists have no repeats. Split everyone into two teams (one of them may be empty) so that no two conflicting people end up on the same team. Return True if this is possible and False otherwise.

Example 1

conflicts=[[1], [0, 2], [1, 3], [2]] → True

The chain 0 — 1 — 2 — 3 splits into teams {0, 2} and {1, 3}.

Example 2

conflicts=[[1, 2], [0, 2], [0, 1], []] → False

Employees 0, 1 and 2 all clash with one another, so two of them would end up on the same team.

Example 3

conflicts=[[], []] → True

There are no conflicts, so any split works.

Constraints

1 ≤ n = len(conflicts) ≤ 100
0 ≤ conflicts[u][i] < n, conflicts[u][i] ≠ u
The values in conflicts[u] are distinct
If v is in conflicts[u], then u is in conflicts[v]

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Union Find Graph

Similar problems

Do the Links Form a Tree Medium Isolated Groups in a Network Medium Ratio Chain Queries Medium Clusters of Linked Servers Medium The Extra Cable Medium

Input

conflicts=[[1], [0, 2], [1, 3], [2]]

Expected

True

Run checks the first 3 tests in your browser. Submit checks all 66 tests on the server, hidden ones included.