A graph whose vertices can be divided into two independent sets, U and V such that every edge (u, v) either connects a vertex from U to V or a vertex from V to U.
‼️AKAAAAAAA‼️
If we are able to color the graph using 2 colors such that no adjacent nodes have the same color.
A graph whose nodes can be divided into two sets such that no two nodes within the same set are adjacent.
If the graph has an odd length cycle, it is not a bipartite graph.
If the graph has an even length cycle, it is said to be a bipartite graph.
In the case of a disconnected graph, if each connected component is bipartite, then the entire graph is considered bipartite. The condition for bipartiteness must hold true for all separate connected components.
def isBipartite(self, graph: List[List[int]]) -> bool:
visited = {}
def dfs(node, color):
if node in visited:
# Check if the color matches the expected one if already visited
return visited[node] == color
visited[node] = color
for neighbor in graph[node]:
# Graph is not bipartite if false for any neighbor
if not dfs(neighbor, 1 - color):
return False
return True
# Iterate over all nodes to ensure disconnected components are checked
for i in range(len(graph)):
if i not in visited:
if not dfs(i, 0):
return False
return True