Is Graph Bipartite?
MediumP3Coding
An undirected graph with n nodes labelled 0..n - 1 is given as an adjacency list: graph[u] lists the neighbours of node u. There are no self-loops or parallel edges, and the graph may be disconnected.
Return true if the nodes can be split into two sets so that every edge connects a node in one set to a node in the other.
Example 1
- Input
- graph = [[1,3],[0,2],[1,3],[0,2]]
- Output
- true
- Why
- Sets {0, 2} and {1, 3}.
Example 2
- Input
- graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
- Output
- false
- Why
- 0, 1, 2 form a triangle.
Constraints
- 1 <= n <= 100
- 0 <= graph[u].length < n
- If v is in graph[u] then u is in graph[v].
Hints
Give it a real attempt first. Run shows which examples fail.
Saved automatically
Run checks the 3 visible tests, Submit all 9. ⌘Enter runs, ⌘⇧Enter submits.