Can Everyone Be Split Into Two Teams

Implement canSplitInTwoTeams

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

Example 1:

Input: graph = [[1,3],[0,2],[1,3],[0,2,4],[3],[]]

Output: true

Example 2:

Input: graph = [[1,2],[0,2],[0,1]]

Output: false

Example 3:

Input: graph = [[]]

Output: true

+ 14 hidden test cases run on Submit.

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

graph =

[[1,3], [0,2], [1,3], [0,2,4], [3], []]