Bipartite Graph
Given an undirected graph represented as an adjacency list, return whether the graph is bipartite.
Constraints
n, m ≤ 250
wheren
andm
are the number of rows and columns ingraph
https://binarysearch.com/problems/Bipartite-Graph
Examples
Example 1
Input
- graph =
[[1],
[0]]
Output
- answer =
True
Explanation
This is bipartite since the node 1
can belong in set A
and node 2
can belong in set B
. Then the edges 0 -> 1
and 1 -> 0
has one node in A
and one node in B
Example 2
Input
- graph =
[[list([1, 2, 3]),list([0, 2]),list([0, 1, 3]),list([0, 2])]]
Output
- answer =
False
Explanation
No matter how the nodes are partitioned, an edge will belong to the same set.
Example 3
Input
- graph =
[[2,3],
[2,3],
[0,1],
[0,1]]
Output
- answer =
True
Explanation
0
and 1
can belong in set A
and 2
and 3
can belong in set B
.
Leave a comment