Problem Statement in English

You’re given an undirected graph, return true if and only if it is bipartite.

Approach

There are 2 approaches to solve this problem, one is using BFS and the other is using DSU. In both approaches, we will try to color the graph using 2 colors. If we can color the graph using 2 colors, then the graph is bipartite.

BFS: We will start from an unvisited node and color it with color 1. Then we will color all its neighbors with color -1. Then we will color all the neighbors of the neighbors with color 1 and so on. If we find a neighbor which is already colored with the same color as the current node, then the graph is not bipartite.

DSU: We will use DSU to group the nodes. We will iterate through the graph and for each node, we will try to union it with its neighbors. If we find a neighbor which is already in the same group as the current node, then the graph is not bipartite.

Solution in Python

  • BFS Solution, Time: $O(n + m)$, Space: $O(n)$

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        l = len(graph)
        color = [0 for _ in range(l)]

        def bfs(node):
            q = deque([node])

            while q:
                node = q.popleft()

                if not color[node]:
                    color[node] = 1
                
                for nei in graph[node]:
                    if not color[nei]:
                        color[nei] = -1 * color[node]
                        q.append(nei)
                    elif color[node] == color[nei]:
                        return False
            return True          
        
        for i in range(l):
            if not color[i] and not bfs(i):
                return False

        return True
  • DSU Solution, Time: $O(n + m)$, Space: $O(n)$

class Solution:
    def isBipartite(self, graph: List[List[int]]) -> bool:
        parent = {}

        def find(x):
            if x not in parent:
                parent[x] = x

            if parent[x] != x:
                parent[x] = find(parent[x])

            return parent[x]

        def union(a, b):
            pa, pb = find(a), find(b)
            parent[b] = pa

        adj = defaultdict(list)

        for i, l in enumerate(graph):
            for element in l:
                adj[i].append(element)
                adj[element].append(i)

        for i in range(len(graph)):
            nei = adj[i]
            this = find(i)

            if not nei: continue

            for j in nei[1:]:
                if this == find(j):
                    return False
                union(nei[0], j)

        return True

And we are done.