Is Graph Bipartite?

▶

Steps

setup

Initialize Union-Find Structure

Create the Union-Find data structure with each node as its own parent and rank zero.

💡 This sets up the disjoint sets where each node starts in its own group, essential for detecting cycles.

Line:

uf = UnionFind(n)

💡 Each node is initially isolated, so no conflicts exist yet.

traverse

Start Processing Node 0

Begin processing node 0 to union its neighbors with the first neighbor.

💡 We process each node to group neighbors and check for conflicts.

Line:

for node in range(n):
    # node = 0

💡 Node 0's neighbors will be unioned to check bipartite conditions.

compare

Check Neighbor 1 of Node 0 for Conflict

Compare the sets of node 0 and neighbor 1 to detect if they are in the same set, which would indicate a conflict.

💡 If node and neighbor are in the same set, the graph is not bipartite.

Line:

if uf.find(node) == uf.find(graph[node][i]):
    return False
# node=0, i=1, neighbor=1

💡 Node 0 and neighbor 1 are in different sets, so no conflict yet.

insert

Union Neighbor 1 with First Neighbor 1 of Node 0

Union the first neighbor of node 0 (which is 1) with neighbor 1 itself, effectively union(1,1).

💡 Union operation groups neighbors to the same set to detect odd cycles.

Line:

uf.union(graph[node][0], graph[node][i])
# union(1,1)

💡 Union of a node with itself is trivial and does not change sets.

compare

Check Neighbor 3 of Node 0 for Conflict

Compare the sets of node 0 and neighbor 3 to detect if they are in the same set, which would indicate a conflict.

💡 Detecting if node and neighbor share the same set prevents odd cycles.

Line:

if uf.find(node) == uf.find(graph[node][i]):
    return False
# node=0, i=2, neighbor=3

💡 Node 0 and neighbor 3 are in different sets, so no conflict.

insert

Union Neighbor 3 with First Neighbor 1 of Node 0

Union the first neighbor of node 0 (1) with neighbor 3 to group them in the same set.

💡 Union groups neighbors to detect if future edges create conflicts.

Line:

uf.union(graph[node][0], graph[node][i])
# union(1,3)

💡 Neighbors 1 and 3 are now in the same set, reflecting one bipartite group.

traverse

Finish Processing Node 0

All neighbors of node 0 processed; mark node 0 as done.

💡 Completing node processing allows moving to next node.

Line:

for node in range(n):
    # finished node 0

💡 Node 0's neighbors are grouped correctly without conflicts.

traverse

Start Processing Node 1

Begin processing node 1 to union its neighbors with the first neighbor.

💡 Process node 1's neighbors to continue grouping sets.

Line:

for node in range(n):
    # node = 1

💡 Node 1's neighbors will be checked for conflicts and unioned.

compare

Check Neighbor 0 of Node 1 for Conflict

Compare the sets of node 1 and neighbor 0 to detect if they are in the same set.

💡 If node and neighbor are in the same set, it indicates a conflict.

Line:

if uf.find(node) == uf.find(graph[node][i]):
    return False
# node=1, i=1, neighbor=0

💡 Node 1 and neighbor 0 are in different sets, so no conflict.

insert

Union Neighbor 0 with First Neighbor 0 of Node 1

Union the first neighbor of node 1 (0) with neighbor 0 itself, effectively union(0,0).

💡 Union operation groups neighbors to detect odd cycles.

Line:

uf.union(graph[node][0], graph[node][i])
# union(0,0)

💡 Union of a node with itself is trivial and does not change sets.

from typing import List

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))  # STEP 1
        self.rank = [0] * n          # STEP 1

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # STEP 3 path compression
        return self.parent[x]

    def union(self, x, y):
        px, py = self.find(x), self.find(y)  # STEP 3 find parents
        if px == py:
            return False  # STEP 3 conflict detected
        if self.rank[px] < self.rank[py]:
            self.parent[px] = py  # STEP 3 union by rank
        elif self.rank[py] < self.rank[px]:
            self.parent[py] = px
        else:
            self.parent[py] = px
            self.rank[px] += 1
        return True

def isBipartite(graph: List[List[int]]) -> bool:
    n = len(graph)  # STEP 1
    uf = UnionFind(n)  # STEP 1

    for node in range(n):  # STEP 2 traverse nodes
        for i in range(1, len(graph[node])):  # STEP 2 traverse neighbors
            if uf.find(node) == uf.find(graph[node][i]):  # STEP 3 compare sets
                return False
            uf.union(graph[node][0], graph[node][i])  # STEP 4 union neighbors
    return True  # STEP 5 no conflicts found

📊

Is Graph Bipartite? - Watch the Algorithm Execute, Step by Step

Watching the algorithm step-by-step reveals how union-find groups nodes and detects odd cycles, which is the key to understanding bipartite checking.

Visiting: none

0

1

2

3

Visiting: 0

0

1

2

3

Visiting: 0

Edge: 0 → 1

0

1

2

3

Visiting: 0

Edge: 0 → 1

0

1

2

3

Visiting: 0

Edge: 0 → 3

0

1

2

3

Visiting: 0

Edge: 0 → 3

0

1

2

3

Visiting: none

0

1

2

3

Visiting: 1

0

1

2

3

Visiting: 1

Edge: 1 → 0

0

1

2

3

Visiting: 1

Edge: 1 → 0

0

1

2

3

Key Takeaways

✓ Union-Find efficiently groups nodes into sets representing bipartite partitions and detects conflicts by checking if two nodes belong to the same set.

This insight is hard to see from code alone because union-find operations are abstract; watching parents and ranks change clarifies the grouping.

✓ The algorithm processes each node's neighbors by unioning them with the first neighbor, ensuring all neighbors are in the opposite set from the node.

Visualizing this step-by-step shows how the bipartite sets form incrementally.

✓ A conflict is detected immediately when a neighbor is found in the same set as the node, indicating the graph is not bipartite.

Seeing the exact moment and condition for conflict detection helps understand why the algorithm returns false early.

Practice

1. Consider the following Python code to find the center of a star graph. What is the value of freq after processing all edges for the input edges = [[1,2],[2,3],[4,2]]?

easy

A. {1: 1, 2: 3, 3: 1, 4: 1}

B. {1: 1, 2: 2, 3: 1, 4: 1}

C. {1: 1, 2: 4, 3: 1, 4: 1}

D. {1: 2, 2: 3, 3: 1, 4: 1}

Solution

1. Step 1: Count frequencies for each edge

   Edges are [1,2], [2,3], [4,2]. Counting occurrences: 1 appears once, 2 appears in all three edges (3 times), 3 once, 4 once.

2. Step 2: Construct frequency dictionary

   freq = {1:1, 2:3, 3:1, 4:1} after processing all edges.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Node 2 appears 3 times, matching n-1=3 for n=4 nodes [OK]

Hint: Count each node's appearance in edges [OK]

Common Mistakes:

• Miscounting frequency of node 2
• Adding extra counts for nodes
• Confusing node labels with counts

2. You are given a matrix representing heights of cells on a grid. Water can flow from a cell to its neighboring cells if the neighbor's height is less than or equal to the current cell's height. Find all cells from which water can flow to both the top-left and bottom-right edges of the grid. Which algorithmic approach guarantees an optimal solution for this problem?

easy

A. Use dynamic programming to store maximum reachable heights and combine results.

B. Run DFS from every cell to check if it can reach both edges independently.

C. Run BFS or DFS starting from the edges inward, marking reachable cells for each edge, then find their intersection.

D. Apply a greedy approach by always moving to the neighbor with the highest height.

Solution

1. Step 1: Understand flow direction

   Water flows from higher or equal height to lower or equal height neighbors, so starting from edges inward ensures we only visit reachable cells.

2. Step 2: Reverse BFS/DFS from edges

   By running BFS/DFS from the edges inward, we mark all cells that can flow to each ocean, then intersect these sets to find cells that can flow to both.

3. Final Answer:

   Option C -> Option C

4. Quick Check:

   Starting from edges avoids repeated DFS from every cell [OK]

Hint: Reverse BFS/DFS from edges is optimal [OK]

Common Mistakes:

• Thinking BFS/DFS must start from each cell
• Using greedy approach fails on plateaus

3. Given the following DFS-based code for rotting oranges, what is the value of max_time after processing the grid [[2,1,1],[1,1,0],[0,1,1]]?

def orangesRotting(grid):
    rows, cols = len(grid), len(grid[0])
    time_grid = [[-1]*cols for _ in range(rows)]
    max_time = 0

    def dfs(r, c, time):
        nonlocal max_time
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return
        if grid[r][c] == 0:
            return
        if time_grid[r][c] != -1 and time_grid[r][c] <= time:
            return
        time_grid[r][c] = time
        max_time = max(max_time, time)
        directions = [(1,0),(-1,0),(0,1),(0,-1)]
        for dr, dc in directions:
            nr, nc = r + dr, c + dc
            if 0 <= nr < rows and 0 <= nc < cols:
                if grid[nr][nc] == 1 or (grid[nr][nc] == 2 and time_grid[nr][nc] > time + 1):
                    dfs(nr, nc, time + 1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == 2:
                dfs(r, c, 0)
    return max_time

easy

A. 3

B. 4

C. 2

D. 5

Solution

1. Step 1: Trace DFS from rotten orange at (0,0) with time=0

   It rots adjacent fresh oranges incrementally, updating time_grid and max_time as rot spreads.

2. Step 2: Follow rot spread minute by minute

   Rot spreads to (0,1) and (1,0) at time=1, then to (0,2), (1,1), and (2,1) at time=2, and finally to (2,2) at time=3.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Maximum rot time matches the longest path from initial rotten orange [OK]

Hint: Max time equals longest rot spread path [OK]

Common Mistakes:

• Off-by-one counting minutes
• Ignoring multiple rotten sources
• Confusing grid indices

4. The following code attempts to count the number of islands in a grid using DFS. Identify the line that contains a subtle bug that can cause incorrect island counting or runtime errors.

def numIslands(grid):
    if not grid:
        return 0
    rows, cols = len(grid), len(grid[0])

    def dfs(r, c):
        if r < 0 or c < 0 or r >= rows or c >= cols:
            return
        if grid[r][c] == '0':
            return
        # Missing visited marking here
        dfs(r+1, c)
        dfs(r-1, c)
        dfs(r, c+1)
        dfs(r, c-1)

    count = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1
    return count

medium

A. Line checking if grid[r][c] == '0'

B. Missing line marking grid[r][c] as visited (e.g., grid[r][c] = '0')

C. Line checking if r or c is out of bounds

D. Line incrementing count after DFS call

Solution

1. Step 1: Identify the purpose of marking visited cells

   Marking visited cells prevents revisiting and infinite recursion or double counting.

2. Step 2: Locate missing visited marking

   The code lacks the line that sets grid[r][c] = '0' inside DFS, so visited land cells are never marked.

3. Final Answer:

   Option B -> Option B

4. Quick Check:

   Without marking visited, DFS revisits same cells causing incorrect counts or infinite loops [OK]

Hint: Always mark visited cells to avoid revisiting [OK]

Common Mistakes:

• Forgetting to mark visited cells
• Incorrect boundary checks

5. What is the time complexity of the optimal bidirectional BFS approach for the Word Ladder problem, where N is the number of words in the dictionary and L is the length of each word?

medium

A. O(N^2 * L)

B. O(N * 26^L)

C. O(N * L^2)

D. O(N * L * 26)

Solution

1. Step 1: Identify operations per word

   For each word, we try changing each of its L letters to 26 possible letters, generating up to 26*L neighbors.

2. Step 2: Consider total words processed

   In worst case, all N words are visited, so total operations are O(N * L * 26).

3. Step 3: Consider the cost of checking each generated word

   Checking if a generated word is in the dictionary (word_set) can be done in O(1) average, but generating each neighbor involves string slicing which is O(L), so total complexity is O(N * L^2).

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Each neighbor generation involves O(L) slicing, repeated for O(N * L * 26) neighbors, resulting in O(N * L^2) complexity [OK]

Hint: Each word generates O(L*26) neighbors, each neighbor generation costs O(L) due to slicing [OK]

Common Mistakes:

• Confusing exponential 26^L with linear 26*L
• Assuming quadratic N^2 due to pairwise checks
• Ignoring string slicing cost in complexity