All problems

Is Graph Bipartite?

Medium · graph traversal

A control panel has n lamps, numbered 0 to n - 1, joined by wires. You are given graph, where graph[i] is the list of lamps that are wired directly to lamp i. Wires work in both directions, so if j is in graph[i] then i is in graph[j]. No lamp is wired to itself, and no wire is listed twice. A lamp may have no wires at all, and the lamps do not have to form one connected piece.

You want to paint every lamp either red or blue so that no wire joins two lamps of the same colour.

Return true if such a painting exists, and false otherwise. The order of the numbers inside each list carries no meaning.

Examples

Example 1

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

Output: true

The four lamps form a square. Paint 0 and 2 red, and 1 and 3 blue.

Example 2

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

Output: false

Lamps 0, 1 and 2 are all wired to each other, so whichever two colours you use, two of them clash.

Example 3

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

Output: true

Lamp 2 has no wires, so it can be any colour, and lamps 0 and 1 take different colours.

Constraints

• 1 <= n <= 10^4
• 0 <= graph[i].length <= n - 1
• The lists hold at most 10^5 numbers in total.
• Every number in graph[i] is in the range 0 to n - 1, is not i, and appears once in that list.
• j is in graph[i] if and only if i is in graph[j].