Is Graph Bipartite?

📋

Problem

Imagine you are organizing a party and want to split guests into two groups such that no two guests who dislike each other end up in the same group. Can you determine if such a split is possible?

Given an undirected graph, determine if it is bipartite. A graph is bipartite if its vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to the other. Input: An integer n representing the number of vertices (0-indexed), and an adjacency list graph where graph[i] is a list of vertices adjacent to vertex i. Output: Return true if the graph is bipartite, otherwise false.

1 ≤ n ≤ 10^50 ≤ graph[i].length ≤ n-10 ≤ graph[i][j] < ngraph[i] does not contain duplicate verticesgraph[i] does not contain i (no self loops)

Edge cases: Graph with a single node → true (trivially bipartite)Graph with no edges → true (no edges to violate bipartite)Graph with disconnected components → true if all components are bipartite

</>

IDE

def isBipartite(graph: List[List[int]]) -> bool:public boolean isBipartite(int[][] graph)bool isBipartite(vector<vector<int>>& graph)function isBipartite(graph)

def isBipartite(graph):
    # Write your solution here
    pass

class Solution {
    public boolean isBipartite(int[][] graph) {
        // Write your solution here
        return false;
    }
}

#include <vector>
using namespace std;

bool isBipartite(vector<vector<int>>& graph) {
    // Write your solution here
    return false;
}

function isBipartite(graph) {
    // Write your solution here
}

Common Bugs to Avoid

Wrong: Incorrectly returning false on empty or single-node graphs due to missing base case handling.✅ Add explicit checks for empty graph (n=0) and single node graphs to return true immediately.

Wrong: Failing to detect odd-length cycles causing incorrect true output.✅ During DFS/BFS, if a neighbor has the same color as current node, return false immediately.

Wrong: Not iterating over all disconnected components, returning false prematurely.✅ Run DFS/BFS coloring on all unvisited nodes to cover disconnected components.

Wrong: TLEUsing exponential backtracking or inefficient approach instead of BFS/DFS coloring.✅ Implement BFS or DFS coloring with O(V+E) complexity to avoid timeouts.

✓

Test Cases

Try testing your solution on graphs with no edges and single nodes to handle base cases.

Focus on detecting odd cycles and handling disconnected components correctly.

Optimize your solution to run in linear time using BFS or DFS coloring.

t1_01basic

Input{"graph":[[1,3],[0,2],[1,3],[0,2]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

We can split vertices into sets {0,2} and {1,3} with edges only between sets.

💡 Try coloring nodes using two colors and check for conflicts.

💡 Use BFS or DFS to assign colors and verify neighbors have opposite colors.

💡 If a neighbor has the same color, return false; otherwise, continue.

Why it failed: Returned false incorrectly - likely missed checking all connected components or color conflicts. Fix by ensuring DFS/BFS colors all nodes and checks neighbors' colors properly.

✓ Correctly identified bipartite graph using proper two-coloring.

t1_02basic

Input{"graph":[[1,2],[0,3],[0,3],[1,2]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Graph contains an odd-length cycle (triangle 0-1-3-0), so it is not bipartite.

💡 Check for odd-length cycles by detecting color conflicts during traversal.

💡 If a node's neighbor has the same color, the graph is not bipartite.

💡 Return false immediately upon detecting a color conflict.

Why it failed: Returned true incorrectly - likely failed to detect odd-length cycle or color conflict. Fix by verifying neighbor colors during DFS/BFS.

✓ Correctly detected non-bipartite graph due to odd cycle.

t2_01edge

Input{"graph":[]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Empty graph (n=0) is trivially bipartite as there are no vertices or edges.

💡 Consider the base case of no nodes in the graph.

💡 An empty graph has no edges to violate bipartite conditions.

💡 Return true immediately if graph is empty.

Why it failed: Returned false on empty graph - likely did not handle n=0 case. Fix by adding a check for empty graph and returning true.

✓ Correctly handled empty graph as bipartite.

t2_02edge

Input{"graph":[[]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Single node with no edges is trivially bipartite.

💡 Check graphs with a single node and no edges.

💡 No edges means no conflicts in coloring.

💡 Return true for single-node graphs.

Why it failed: Returned false for single node graph - likely failed to handle isolated nodes. Fix by ensuring single nodes without edges return true.

✓ Correctly identified single node graph as bipartite.

t2_03edge

Input{"graph":[[],[],[]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Graph with multiple disconnected nodes and no edges is bipartite.

💡 Consider disconnected components with no edges.

💡 Each isolated node can be colored arbitrarily.

💡 Return true if all components are bipartite.

Why it failed: Returned false on disconnected graph with no edges - likely failed to handle disconnected components. Fix by iterating over all nodes and coloring each component.

✓ Correctly handled disconnected graph with no edges as bipartite.

t3_01corner

Input{"graph":[[1,2],[0,2],[0,1]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Graph contains an odd-length cycle (triangle 0-1-2-0), which makes it non-bipartite.

💡 Beware of odd-length cycles causing non-bipartite graphs.

💡 Check if your algorithm detects cycles and their parity correctly.

💡 Return false if an odd cycle is detected during coloring.

Why it failed: Returned true on graph with odd cycle - likely failed to detect odd cycle or color conflict. Fix by checking neighbor colors during DFS/BFS.

✓ Correctly detected odd cycle and returned false.

t3_02corner

Input{"graph":[[1],[0,2],[1,3],[2]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Graph with multiple components, all bipartite.

💡 Ensure your solution handles disconnected components.

💡 Run DFS/BFS on all unvisited nodes.

💡 Return true only if all components are bipartite.

Why it failed: Returned false on disconnected bipartite graph - likely failed to check all components. Fix by iterating over all nodes and running DFS/BFS on each.

✓ Correctly handled disconnected bipartite graph.

t3_03corner

Input{"graph":[[1,2],[0,2],[0,1],[4],[3]]}

Expectedfalse

⏱ Performance - must finish in 2000ms

Graph contains an odd-length cycle (triangle 0-1-2-0), making it non-bipartite.

💡 Check for odd cycles formed by triangles.

💡 Verify that no self loops exist as per constraints.

💡 Return false if odd cycle detected.

Why it failed: Returned true on graph with odd cycle - likely missed color conflict detection. Fix by verifying neighbor colors during traversal.

✓ Correctly detected odd cycle and returned false.

t4_01performance

Input{"graph":[[1],[0,2],[1,3],[2,4],[3,5],[4,6],[5,7],[6,8],[7,9],[8,10],[9,11],[10,12],[11,13],[12,14],[13,15],[14,16],[15,17],[16,18],[17,19],[18,20],[19,21],[20,22],[21,23],[22,24],[23,25],[24,26],[25,27],[26,28],[27,29],[28,30],[29,31],[30,32],[31,33],[32,34],[33,35],[34,36],[35,37],[36,38],[37,39],[38,40],[39,41],[40,42],[41,43],[42,44],[43,45],[44,46],[45,47],[46,48],[47,49],[48,50],[49,51],[50,52],[51,53],[52,54],[53,55],[54,56],[55,57],[56,58],[57,59],[58,60],[59,61],[60,62],[61,63],[62,64],[63,65],[64,66],[65,67],[66,68],[67,69],[68,70],[69,71],[70,72],[71,73],[72,74],[73,75],[74,76],[75,77],[76,78],[77,79],[78,80],[79,81],[80,82],[81,83],[82,84],[83,85],[84,86],[85,87],[86,88],[87,89],[88,90],[89,91],[90,92],[91,93],[92,94],[93,95],[94,96],[95,97],[96,98],[97,99],[98],[99]]}

Expectedtrue

⏱ Performance - must finish in 2000ms

Linear chain graph with n=100 nodes and n-1 edges, bipartite by nature. Algorithm must run in O(V+E) time within 2 seconds.

💡 Use BFS or DFS with coloring to achieve O(V+E) time complexity.

💡 Avoid exponential backtracking approaches.

💡 Iterate over all nodes and color components efficiently.

Why it failed: TLE due to exponential or inefficient approach. Fix by implementing BFS/DFS coloring with O(V+E) complexity.

✓ Efficient O(V+E) solution confirmed by passing performance test.

Practice

1. Consider the following BFS-based cloneGraph function. Given the input graph with nodes 1 connected to 2 and 3, and node 2 connected to 3, what is the value of the neighbors list of the cloned node corresponding to node 1 after the first iteration of the while loop (i.e., after processing node 1)?

easy

A. A list containing cloned nodes with values [2, 3]

B. An empty list []

C. A list containing cloned nodes with values [1]

D. A list containing cloned nodes with values [3, 2]

Solution

1. Step 1: Trace the first iteration of the while loop

   Initially, queue contains node 1. We pop node 1 and iterate over its neighbors: nodes 2 and 3.

2. Step 2: Update visited and neighbors

   Nodes 2 and 3 are not visited, so they are cloned and added to visited and queue. Then, the cloned node 1's neighbors list is appended with cloned nodes 2 and 3 in order.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Neighbors of cloned node 1 after first iteration are clones of nodes 2 and 3 [OK]

Hint: Neighbors appended in order during BFS iteration [OK]

Common Mistakes:

• Assuming neighbors list is empty after first iteration
• Mixing up order of neighbors appended

2. You are given an n x n grid where each cell is either 0 (walkable) or 1 (blocked). You need to find the shortest path from the top-left corner to the bottom-right corner, moving in 8 possible directions (including diagonals). Which algorithmic approach guarantees finding the shortest path efficiently in this scenario?

easy

A. Breadth-First Search (BFS) using a queue to explore neighbors level by level

B. Depth-First Search with backtracking to explore all paths

C. Greedy Best-First Search prioritizing cells closest to the target

D. Dynamic Programming to store shortest paths to each cell

Solution

1. Step 1: Understand the problem constraints

   The grid allows movement in 8 directions and requires the shortest path from start to end.

2. Step 2: Identify the algorithm that guarantees shortest path in unweighted graphs

   BFS explores neighbors level by level, ensuring the first time we reach the target is via the shortest path.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   BFS is the classic shortest path algorithm for unweighted grids [OK]

Hint: Shortest path in unweighted grid -> BFS [OK]

Common Mistakes:

• Thinking DFS finds shortest path
• Using greedy heuristics without guarantees

3. What is the time complexity of the optimal BFS approach that starts from all land cells simultaneously in an n x n grid?

medium

A. O(n^2) for BFS plus O(n^2) for initializing the distance matrix, totaling O(n^2).

B. O(n^2) because each cell is enqueued and processed at most once.

C. O(n^3) because BFS explores neighbors for each cell multiple times.

D. O(n^4) because BFS is run from each land cell separately.

Solution

1. Step 1: Each cell is enqueued at most once because distance is updated only when -1.

   Thus, BFS processes O(n^2) cells.

2. Step 2: Each cell has up to 4 neighbors checked, so total operations are O(4*n^2) = O(n^2).

   Initialization is also O(n^2), so total complexity is O(n^2) + O(n^2) = O(n^2).

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Multi-source BFS runs in linear time relative to grid size including initialization [OK]

Hint: Each cell visited once in BFS -> O(n^2) time including initialization [OK]

Common Mistakes:

• Assuming BFS runs from each land cell separately
• Counting neighbors multiple times incorrectly
• Confusing initialization cost with BFS cost

4. Suppose the Keys and Rooms problem is modified so that keys can be reused infinitely (i.e., you can revisit rooms multiple times). Which of the following changes to the algorithm is necessary to correctly determine if all rooms can be visited?

hard

A. Remove the visited array and perform DFS without tracking visited rooms

B. Use BFS with a queue and mark rooms as visited when enqueued to avoid infinite loops

C. Keep the visited array but reset it after each DFS call to allow revisits

D. Use a counter to limit the number of visits per room to prevent infinite recursion

Solution

1. Step 1: Understand infinite reuse of keys means cycles are possible

   Without marking visited before enqueueing, BFS can enqueue the same room multiple times causing inefficiency or infinite loops.

2. Step 2: Use BFS with visited marking on enqueue

   Marking visited when enqueuing prevents multiple enqueues of the same room, ensuring termination and correctness.

3. Step 3: Why other options fail

   Removing visited causes infinite loops; resetting visited loses progress; limiting visits is inefficient and complex.

4. Final Answer:

   Option B -> Option B

5. Quick Check:

   BFS with visited marking on enqueue is standard for graphs with cycles [OK]

Hint: Mark visited when enqueuing in BFS to handle cycles [OK]

Common Mistakes:

• Removing visited causes infinite loops
• Resetting visited loses track of progress
• Counting visits is inefficient and unnecessary

5. Suppose the problem changes: fresh oranges can become rotten multiple times, and rot can spread back to previously rotten oranges if it results in a faster rot time. Which modification to the DFS-based solution correctly handles this scenario?

hard

A. Switch to a brute force simulation updating the grid minute by minute until no changes

B. Keep the original DFS with pruning but run it multiple times until no updates occur

C. Use a multi-source BFS but do not track times, just mark visited once

D. Remove the pruning condition that skips DFS if time_grid[r][c] <= time, allowing revisits with better times

Solution

1. Step 1: Understand new rot dynamics

   Rot can improve previously recorded rot times, so pruning based on time_grid[r][c] <= time is invalid.

2. Step 2: Modify DFS to allow revisits with better times

   Removing pruning condition enables DFS to update time_grid when a faster rot path is found.

3. Step 3: Confirm correctness

   This ensures all cells have minimum rot times even if rot spreads back to previously rotten oranges.

4. Final Answer:

   Option D -> Option D

5. Quick Check:

   Allowing revisits with better times handles dynamic rot spread correctly [OK]

Hint: Allow revisits if they improve rot time [OK]

Common Mistakes:

• Keeping pruning causes stale times
• Using BFS without time tracking
• Brute force is inefficient