Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Is Graph Bipartite?
Bookmark
BFS
DFS
Union Find
Input
Odd cycle inside
Square
Triangle
Hexagon
Custom
graph
=
[[1,2,3],[0,2],[0,1,3],[0,2]]
0
1
2
3
A
B
0
1
2
3
A
B
0
1
2
3
color[0] == -1 → queue [
0
] paint
A
A
0
B
0
1
2
3
dequeue 0
color =
A
queue = []
A
0
B
0
1
2
3
color[1] ←
B
(opposite of
A
)
A
0
B
1
0
1
2
3
color[2] ←
B
(opposite of
A
)
A
0
B
1
2
0
1
2
3
color[3] ←
B
(opposite of
A
)
A
0
B
1
2
3
0
1
2
3
dequeue 1
color =
B
queue = [2, 3]
A
0
B
1
2
3
0
1
2
3
color[0] =
A
≠
B
edge ok
A
0
B
1
2
3
0
1
2
3
color[2] =
B
==
color[1]
conflict
A
0
B
1
2
3
return false
0
1
2
3
A
0
B
1
2
3
algo
master
.
io
Step:
Try to split the 4 nodes into two sets, A and B, so every edge crosses between them
0 / 11
Input
Odd cycle inside
Square
Triangle
Hexagon
Custom
graph
=
[[1,2,3],[0,2],[0,1,3],[0,2]]
0 / 11
algo
master
.
io
Step:
Try to split the 4 nodes into two sets, A and B, so every edge crosses between them
