Loading problem…
There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B. Return true if and only if it is bipartite.
Example 1
Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: Put nodes 0 and 2 in one set and nodes 1 and 3 in the other. Every edge (0-1, 0-3, 2-1, 2-3) connects the two sets.
Example 2
Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: Nodes 0, 1 and 2 are all connected to each other in a triangle. Two of them would always have to share a set, so the graph is not bipartite.
Example 3
Input: graph = [[1],[0]]
Output: true
Explanation: Put node 0 in one set and node 1 in the other. The only edge connects the two sets.
Try to 2-color the graph: give each node a color opposite its neighbours. A conflict (a neighbour already has the same color) proves it is not bipartite.
Run checks all cases above. Submit evaluates all test cases.