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.
OR A bipartite graph is a graph if and only if it contains no odd cycles.
Two-coloring Method – O(n + m)
Method Purpose: To determine whether a graph is bipartite (i.e., whether its vertices can be colored with two colors such that no two adjacent vertices share the same color).
UNCOLORED, A, B = -1, 0, 1
def is_bipartite_dfs(adj):
"""Return True if graph is bipartite using DFS coloring."""
n = len(adj) - 1
color = [UNCOLORED] * (n + 1)
def dfs(u, c):
color[u] = c
for v in adj[u]:
if color[v] == UNCOLORED:
if not dfs(v, A if c == B else B):
return False
elif color[v] == c:
return False
return True
for u in range(n):
if color[u] == UNCOLORED:
if not dfs(u, A):
return False
return True
def is_bipartite_bfs(adj):
"""Return True if graph is bipartite using BFS coloring."""
n = len(adj) - 1
color = [UNCOLORED] * (n + 1)
for s in range(1, n + 1):
if color[s] != UNCOLORED:
continue
color[s] = A
q = deque([s])
while q:
u = q.popleft()
for v in adj[u]:
if color[v] == UNCOLORED:
color[v] = A if color[u] == B else B
q.append(v)
elif color[v] == color[u]:
return False
return TrueKuhn Algorithm – O(nm)
import sys
def kuhn_max_matching(n1, n2, adj):
"""
n1: # of left vertices (1..n1)
n2: # of right vertices (1..n2)
adj[u]: list of right vertices v reachable from left vertex u
Returns:
res : maximum matching size
matchL : size n1+1, matchL[u] = matched right v or 0 if unmatched
matchR : size n2+1, matchR[v] = matched left u or 0 if unmatched
"""
matchR = [0] * (n2 + 1) # right -> left
def dfs(u, seen):
for v in adj[u]:
if seen[v]:
continue
seen[v] = True
if matchR[v] == 0 or dfs(matchR[v], seen):
matchR[v] = u
return True
return False
res = 0
for u in range(1, n1 + 1):
seen = [False] * (n2 + 1)
if dfs(u, seen):
res += 1
matchL = [0] * (n1 + 1) # left -> right
for v in range(1, n2 + 1):
u = matchR[v]
if u:
matchL[u] = v
return res, matchL, matchR