PPractick

The problem

A school wants to split students into two teams so that every pair of rivals (an edge) ends up on different teams. That's possible exactly when the rivalry graph is bipartite. Try to 2-colour it with DFS: give the start vertex colour 0, give every neighbour the opposite colour, and continue. If you ever find an edge whose two endpoints have the same colour, it's impossible, which happens exactly when the graph has an odd cycle. Components are coloured independently.

Example: [[1,3], [0,2], [1,3], [0,2]] (a 4-cycle) → true; [[1,2,3], [0,2], [0,1,3], [0,2]] → false.

Function signature

bool isBipartite(const vector<vector<int>>& graph);  // undirected adjacency list

Test cases

Input (adjacency list)	Output	Explanation
[[1,3],[0,2],[1,3],[0,2]]	true	Teams {0, 2} and {1, 3}
[[1,2,3],[0,2],[0,1,3],[0,2]]	false	Triangle 0-1-2
[[1,2],[0,2],[0,1]]	false	A triangle is an odd cycle
[[],[2],[1]]	true	Disconnected; 0 is isolated
[[1],[0],[3],[2]]	true	Two separate edges

(Confirm: the graph is undirected and may be disconnected; no self-loops.)

How interviewers phrase it

• "Given an undirected graph, return true if and only if it is bipartite" (LeetCode 785), to be solved with DFS.

Clarifying questions to ask

1. Can the graph be disconnected? (Yes, so colour every component.)
2. Self-loops? (None. A self-loop would make it non-bipartite.)
3. Size? (Up to 100 vertices here; the method is linear anyway.)

Follow-ups to expect

1. "Why does a conflict prove it's impossible?"
2. "Why is the colouring forced?"
3. "BFS version?"
4. "Union-find version?"
5. "Complexity?"

Related questions

• Detect a cycle in an undirected graph Hard
• Cycle Detection in Directed Graph (DFS) Hard
• Topo Sort Hard
• Detect a cycle in a directed graph Hard
• Course Schedule I Hard
• Find eventual safe states Hard

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in