Learn
Practice
Newsletter
Resources
Mobile
New
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Is Graph Bipartite?
Bookmark
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
0
1
2
3
current
color[0] =
A
A
0
B
0
1
2
3
current
neighbors of 0:
[1, 2, 3]
A
0
B
0
1
1
2
3
current
color[1] =
B
A
0
B
1
0
1
2
3
current
color[0] =
A
≠
B
edge ok
A
0
B
1
0
1
2
3
current
color[2] ←
A
(opposite of
B
)
A
0
B
1
0
1
2
3
current
neighbors of 2:
[0, 1, 3]
A
0
2
B
1
0
1
2
3
current
dfs(2) → false, bubble up
A
0
2
B
1
0
1
2
3
current
dfs(1) → false, bubble up
A
0
2
B
1
return false
0
1
2
3
A
0
2
B
1
algo
master
.
io
Step:
Try to split the 4 nodes into two sets, A and B, so every edge crosses between them
0 / 15
Input
Odd cycle inside
Square
Triangle
Hexagon
Custom
graph
=
[[1,2,3],[0,2],[0,1,3],[0,2]]
0 / 15
algo
master
.
io
Step:
Try to split the 4 nodes into two sets, A and B, so every edge crosses between them
