a bipartite graph is a graph that there exists a partition on its vertices such that all edges connect vertices from different groups.
to check if a given graph is bipartite, one can check if it is two-colorable using DFS or BFS.
def dfs(v, color):
colors[v] = color
for u in adj[v]:
if colors[u] == -1:
if not dfs(u, 1 - color):
return False
elif colors[u] == colors[v]:
return False
return True
def is_bipartite():
for v in range(n):
if colors[v] == -1:
if not dfs(v, 0):
return False
return True