Bipartite Algorithm Intro

Intro

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other.

No edge exists between vertices within the same set Commonly used in matching problems, scheduling, and network flows Can be checked using BFS or DFS coloring techniques

Graph Requirements

Directed or Undirected
Represented Using:
- Adjacency List
- Adjacency Matrix

Output

True or False whether the graph is bipartite Optionally, the two sets of vertices if it is bipartite

Video Animation

Bipartite: https://www.youtube.com/watch?v=Zg6UAnAzGGs

BFS Pseudo Code

    from collections import deque

    def is_bipartite(graph):

        color = {}

        for node in graph:
            if node not in color:
                queue = deque([node])
                color[node] = 0  # start coloring with 0

                while queue:
                    u = queue.popleft()
                    for v in graph[u]:
                        if v not in color:
                            color[v] = 1 - color[u]  # alternate color
                            queue.append(v)
                        elif color[v] == color[u]:
                            return False  # conflict detected

        return True

DFS Pseudo Code

    def is_bipartite_dfs(graph):
        color = {}

        def dfs(node, c):
            color[node] = c
            for neighbor in graph[node]:
                if neighbor not in color:
                    if not dfs(neighbor, 1 - c):
                        return False
                elif color[neighbor] == c:
                    return False
            return True

        for node in graph:
            if node not in color:
                if not dfs(node, 0):
                    return False

        return True

Time Complexity

Each vertex is visited once Each edge is processed once

O(V + E)

Space Complexity

Color map: O(V) BFS queue: O(V) DFS recursion stack: O(V)

IRL Use Case

Matching Problems Job assignments or tasks
Network Flows Bipartite graphs are foundational for max flow/min cut problems
Scheduling Two groups that must not conflict

785. Is Graph Bipartite ::1:: - Medium

Topics: Depth First Search, Breadth First Search, Union Find, Graph Theory

Intro

There is an undirected graph with n nodes, where each node is numbered between 0 and n - 1. You are given a 2D array graph, where graph[u] is an array of nodes that node u is adjacent to. More formally, for each v in graph[u], there is an undirected edge between node u and node v. The graph has the following properties: There are no self-edges (graph[u] does not contain u). There are no parallel edges (graph[u] does not contain duplicate values). If v is in graph[u], then u is in graph[v] (the graph is undirected). The graph may not be connected, meaning there may be wo nodes u and v such that there is no path between them. 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. Return true if and only if it is bipartite.

Example Input	Output
graph = [[1,2,3],[0,2],[0,1,3],[0,2]]	false
graph = [[1,3],[0,2],[1,3],[0,2]]	true

Constraints:

graph.length == n

1 ≤ n ≤ 100

0 ≤ graph[u].length <

0 ≤ graph[u][i] ≤ n-1

graph[u] does not contain u

All the values of graph[u] are unique

If graph[u] contains v, then graph[v], contains u

Abstraction

Given a graph, determine if it is bipartite

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: [Bipartite] Topological Sort using BFS - Advanced Graphs/Advanced Graphs


    def isBipartite(self, graph: List[List[int]]) -> bool:
        
        from collections import deque
        from typing import List

        # Initialization
        n = len(graph)              # number of nodes
        color = [0] * n             # 0 = uncolored, 1 = color A, -1 = color B
        
        # Traverse all components (graph may be disconnected)
        for i in range(n):
            if color[i] != 0:
                continue            # already colored in a previous BFS
            
            # Start BFS from uncolored node i
            queue = deque([i])
            color[i] = 1             # assign initial color
            
            # BFS traversal for coloring
            while queue:
                node = queue.popleft()
                
                # Explore neighbors
                for nei in graph[node]:
                    
                    if color[nei] == 0:
                        # Neighbor uncolored: assign opposite color
                        color[nei] = -color[node]
                        queue.append(nei)
                    
                    elif color[nei] == color[node]:
                        # Neighbor already colored same as current: conflict
                        # Graph is not bipartite
                        return False
        
        # If all nodes processed without conflict: bipartite
        return True

886. Possible Bipartition ::1:: - Medium

Topics: Depth First Search, Breadth First Search, Union Find, Graph Theory

Intro

We want to split a group of n people (labeled from 1 to n) into two groups of any size. Each person may dislike some other people, and they should not go into the same group. Given the integer n and the array dislikes where dislikes[i] = [ai, bi] indicates that the person labeled ai does not like the person labeled bi, return true if it is possible to split everyone into two groups in this way.

Example Input	Output
n = 4, dislikes = [[1,2],[1,3],[2,4]]	true
n = 3, dislikes = [[1,2],[1,3],[2,3]]	false

Constraints:

1 ≤ n ≤ 2000

0 ≤ dislikes.length ≤ 10^4

dislikes[i].length == 2

1 ≤ ai < bi ≤ n

All the pairs of dislikes are unique

Abstraction

Wow!

Space & Time Complexity

Solution	Time Complexity	Space Complexity	Time Remark	Space Remark

Bug	Error

Brute Force:

Aspect	Time Complexity	Space Complexity	Time Remarks	Space Remarks

Find the Bug:

Solution 1: [Bipartite] Topological Sort using BFS - Advanced Graphs/Advanced Graphs

    def possibleBipartition(self, n, dislikes):
        # Build graph
        graph = defaultdict(list)
        for a, b in dislikes:
            graph[a].append(b)
            graph[b].append(a)

        # 0 = uncolored, 1 / -1 = two groups
        color = [0] * (n + 1)

        # Handle disconnected components
        for person in range(1, n + 1):
            if color[person] != 0:
                continue

            queue = deque([person])
            color[person] = 1

            while queue:
                cur = queue.popleft()

                for nei in graph[cur]:
                    # conflict → same color
                    if color[nei] == color[cur]:
                        return False

                    if color[nei] == 0:
                        color[nei] = -color[cur]
                        queue.append(nei)

        return True

LeetCode: Graphs II Bipartite