DSA sheet · Graphs · 2-colouring pattern

Is Graph Bipartite?

Can we split the nodes of a graph into two teams so that every edge joins two different teams? The teacher explains the real definition (two groups), then switches to the version everyone uses in practice: give each node one of two colours, and give every neighbour the opposite colour. If a neighbour already has your colour, the graph is not bipartite. She stores the colours as 1 and −1 in one array that also acts as the visited array (0 = not visited), solves it with DFS, fixes a bug in her main loop on screen, and then shows the BFS version. The graph may be split into several pieces, so every piece must be checked.

Every part below follows the same order:
① the question in simple words → ② what the constraints tell us → ③ intuition → ④ building the logic from examples → ⑤ approach steps → ⑥ code → ⑦ code line by line → ⑧ dry run → ⑨ complexity & remember

• Part 0 · Graph basics this page needs
• Part A · 2-colouring with DFS (the teacher's code)
• Part B · 2-colouring with BFS
• Part C · Revision page

Part 0 · Graph basics this page needs

Nodes and edges

A graph is a set of nodes (points, here numbered 0 to n−1) joined by edges (lines). Two nodes joined by an edge are neighbours (the teacher often calls them "children" of the node we're standing on).

Directed, undirected, weighted

Three ways the input can arrive, and the adjacency list

In this problem we are given the adjacency list directly: graph[u] is the list of u's neighbours. So, as the teacher points out, there is nothing to build. If you ever get an edge list instead, this is how you'd convert it:

n = 4
edges = [[0, 1], [0, 3], [1, 2], [2, 3]]
graph = [[] for _ in range(n)]
for u, v in edges:
    graph[u].append(v)
    graph[v].append(u)          # both directions
print(graph)                    # [[1, 3], [0, 2], [1, 3], [0, 2]]

The visited array, and why we can't skip it

The teacher repeats this in every video: around 90% of graph problems need a visited record. In an undirected graph, 0 lists 1 and 1 lists 0 back, so without a record we would bounce between them forever. You can keep a separate True/False array, or, when possible, reuse an array you already need by giving it special values. That's what we'll do here: one array holds 0 (not visited) or a colour (visited).

Connected components

A connected component is a group of nodes that can all reach each other. The problem warns that the graph may not be connected (recall Number of Provinces, where we counted these groups). So a single traversal from node 0 might not see everything. The fix is the usual outer loop: for every node, if it's not visited, start a new traversal from it.

(0)—(1)      (4)—(5)
 |    |         \ /
(3)—(2)         (6)
two components: {0,1,2,3} and {4,5,6}

BFS and DFS

from collections import deque

graph = [[1, 3], [0, 2], [1, 3], [0, 2], [5, 6], [4, 6], [4, 5]]
n = len(graph)

seen = [False] * n
order = []
def dfs(u):
    seen[u] = True
    order.append(u)
    for v in graph[u]:
        if not seen[v]:
            dfs(v)
for i in range(n):
    if not seen[i]:
        dfs(i)
print(order)                    # [0, 1, 2, 3, 4, 5, 6]

seen = [False] * n
order = []
for i in range(n):
    if not seen[i]:
        seen[i] = True
        q = deque([i])
        while q:
            u = q.popleft()
            order.append(u)
            for v in graph[u]:
                if not seen[v]:
                    seen[v] = True
                    q.append(v)
print(order)                    # [0, 1, 3, 2, 4, 5, 6]

New idea for this page: 2-colouring

Colour the start node with colour A. Every neighbour gets colour B, their neighbours get A again, and so on: the colour flips at every edge. If we ever find an edge whose two ends have the same colour, the flip rule has been broken, and no 2-team split is possible. That is the whole pattern.

Part A · 2-colouring with DFS

LeetCode 785 · Is Graph Bipartite?

1The question in simple words

You get an undirected graph with n nodes (0 to n−1) as an adjacency list graph. The graph is bipartite if you can split all nodes into two groups, A and B, so that every edge has one end in A and the other end in B. In other words, no edge joins two members of the same group. Return True or False.

(0)———(1)
 | \    |
 |   \  |
 |     \|
(3)———(2)
edges: 0-1 0-2 0-3 1-2 2-3

(0)———(1)
 |      |
 |      |
(3)———(2)
edges: 0-1 0-3 1-2 2-3

Reading the input: graph[0] = [1,2,3] means node 0 has edges to 1, 2 and 3. graph[1] = [0,2] means 1 is joined to 0 and 2, and so on. Since the graph is undirected, every edge shows up in both lists.

2What the constraints tell us

• 1 ≤ n ≤ 100 → small. Any O(n + E) or even O(n²) idea is instant. Recursion depth is at most 100, so DFS is safe in Python.
• No self-edges (u is never in graph[u]) and no duplicate edges. Good: a self-edge would join a node to itself, same group, instantly not bipartite; we don't have to think about it.
• If v is in graph[u], then u is in graph[v]: it really is undirected.
• The graph may not be connected. This one line decides the shape of the main function (see ④).
• Brute force would try every way to put n nodes into 2 groups: 2ⁿ splits. With n = 100 that's 2¹⁰⁰, hopeless. We need something linear.

3Intuition: alternate the teams

The teacher tries Example 1 by hand: put 0 in A, 1 in B, 2 in A, 3 in B. The idea behind "alternating": a node and its neighbour must be in different groups, so as you walk along edges the group must keep switching A, B, A, B…

  A        B
(0)———(1)
 | \    |
 |   \  |          edge 0-2: A and A  ✗
 |     \|
(3)———(2)
  B        A

Edges 0-1, 1-2, 2-3, 3-0 are all fine (A–B). But edge 0-2 joins two A's. And there was no other choice: once 0 is A, its neighbour 1 is forced to be B, and then 1's neighbour 2 is forced to be A. So Example 1 is not bipartite. In Example 2 the same alternation works on every edge, so it's bipartite.

4Building the logic step by step

Which values to store?

We could store the strings "red" and "yellow", but we only need two values, so numbers are simpler. The teacher picks 1 for red and −1 for yellow, and keeps 0 for "not visited yet".

What happens at one node

We arrive at node with a colour. First mark it: color[node] = c. Then look at each neighbour (child):

• Child not visited (0) → visit it with the opposite colour: dfs(child, -c). If that deeper call ever reports False, pass False straight up.
• Child already visited, different colour → this edge joins A and B. Fine, nothing to do.
• Child already visited, same colour as us → this edge joins two nodes of the same group. Return False.

If the loop over children finishes without any problem, return True: this node and everything explored below it is fine.

The main function: check every component

Because the graph may be in pieces, loop i from 0 to n−1. Whenever color[i] == 0 (a node no earlier search reached, so a new component), start dfs(i, 1). If any component returns False, the whole answer is False. If every component passes, return True.

(0)—(1)      (4)—(5)
 |    |         \ /
(3)—(2)         (6)
square: bipartite ✓      triangle: 4=A, 5=B, 6 must differ from both ✗
answer: False (one bad piece is enough)

The bug she fixed on screen

Her first version of the main loop called dfs(i, 1) for every i, without checking whether i was already coloured. The fix: only call it when color[i] == 0. Why it matters, on the tiny graph (0)—(1):

1. i = 0: dfs(0, 1) colours 0 = 1, then 1 = −1. Fine, True.
2. i = 1 (buggy): dfs(1, 1) overwrites node 1 with colour 1. Its neighbour 0 also has colour 1 → "same colour" → False. But a single edge is obviously bipartite!

With the check, i = 1 is skipped because it's already coloured, and the answer is True. (Even when the buggy version gets lucky, it re-walks whole components again and again.)

5Approach steps

1. n = len(graph); color = [0] * n.
2. For each node i with color[i] == 0: if dfs(i, 1) is False → return False.
3. dfs(node, c): set color[node] = c. For each child: if 0 → recurse with -c (pass False up); else if color[child] == c → return False.
4. dfs returns True after its loop; the main function returns True after its loop.

6Code (Python)

class Solution:
    def isBipartite(self, graph):
        n = len(graph)
        color = [0] * n                     # 0 = not visited, 1 / -1 = the two colours

        def dfs(node, c):
            color[node] = c
            for child in graph[node]:
                if color[child] == 0:
                    if not dfs(child, -c):  # child gets the opposite colour
                        return False
                elif color[child] == c:     # same colour on both ends of an edge
                    return False
            return True

        for i in range(n):
            if color[i] == 0:               # a new component
                if not dfs(i, 1):
                    return False
        return True

7Code line by line

8Dry run

Example 2 (square): expected True

(0 R)———(1 Y)
  |        |
(3 Y)———(2 R)
every edge R–Y ✓

Example 1: expected False

(0 R)———(1 Y)
    \       |
      \     |
       (2 R)       edge 0-2: R and R ✗

Node 3 was never even reached: the first clash ends everything.

9Complexity & remember

• Time O(n + E), where E is the number of edges. Every node is coloured once, and from each node we scan its adjacency list once. The teacher counts it like this: the lengths of all the adjacency lists add up to 2 × E (every undirected edge is stored at both ends; she calls these counts the in-degrees). So the total is n + 2E, which is linear.
• Space O(n): the colour array, plus up to n calls waiting on the recursion stack.

Part B · 2-colouring with BFS

The teacher shows that the same check works level by level with a queue. Steps ①–④ are the same as Part A: same colour array, same three cases for a neighbour, same loop over every component. What changes:

• Instead of recursion, a deque holds the nodes whose neighbours we still have to look at.
• When we colour an unvisited child (-color[node]), we push it, so its own neighbours are checked later.
• When we find a clash, return False immediately ends the whole function. In DFS a return only ended one call and had to be passed up; here everything happens inside the main function, so one return is enough.

5Approach steps

1. For every node i with color[i] == 0: colour it 1 and push it.
2. While the queue isn't empty: pop node; for each child:
3. child 0 → color[child] = -color[node], push it.
4. child has the same colour as node → return False.
5. After all components → return True.

6Code (Python)

from collections import deque

class Solution:
    def isBipartite(self, graph):
        n = len(graph)
        color = [0] * n

        for i in range(n):
            if color[i] != 0:
                continue                         # already checked with its component
            color[i] = 1
            q = deque([i])
            while q:
                node = q.popleft()
                for child in graph[node]:
                    if color[child] == 0:
                        color[child] = -color[node]   # opposite colour
                        q.append(child)
                    elif color[child] == color[node]:
                        return False             # ends the whole function
        return True

7Code line by line

8Dry run

Example 2 (square): expected True

Example 1: expected False

Here the clash shows up on edge 1-2 (both are neighbours of 0, so both are on level 1 with the same colour). DFS found it on edge 0-2. Different edge, same verdict: the triangle 0-1-2 can't be 2-coloured.

9Complexity & remember

• Time O(n + E), space O(n) (colour array + queue). Same as DFS.
• On LeetCode the BFS version ran a little slower; the teacher puts it down to the extra work the queue does internally (every node pushed and popped).

Part C · Revision page

s = Solution()
print(s.isBipartite([[1, 2, 3], [0, 2], [0, 1, 3], [0, 2]]))   # False
print(s.isBipartite([[1, 3], [0, 2], [1, 3], [0, 2]]))         # True
print(s.isBipartite([[1], [0]]))                               # True
print(s.isBipartite([[1, 3], [0, 2], [1, 3], [0, 2], [5, 6], [4, 6], [4, 5]]))   # False
print(s.isBipartite([[]]))                                     # True

Based on this video: Is Graph Bipartite? | Graph | Pattern-wise DSA sheet