Determine Whether an Undirected Graph Is Two-Colorable
Company: Apple
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
# Determine Whether an Undirected Graph Is Two-Colorable
Given an undirected graph with nodes labeled `0` through `n - 1`, determine whether every node can be assigned one of two colors so that the endpoints of every edge have different colors.
```python
def is_two_colorable(n: int, edges: list[list[int]]) -> bool:
...
```
The graph can be disconnected and can contain isolated nodes. Using only one of the two colors in an isolated component is allowed. Parallel edges may appear and do not change the answer; a self-loop makes the answer `false`.
## Constraints
- `0 <= n <= 200_000`
- `0 <= len(edges) <= 300_000`
- Every edge is a pair `[u, v]` with `0 <= u, v < n`.
- Target complexity: `O(n + len(edges))` time and `O(n + len(edges))` space.
## Examples
```text
Input: n = 4, edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
Output: true
```
```text
Input: n = 3, edges = [[0, 1], [1, 2], [2, 0]]
Output: false
```
```text
Input: n = 5, edges = [[0, 1], [3, 4]]
Output: true
```
Quick Answer: Determine whether every component of an undirected graph can be colored with two colors so adjacent nodes differ. The problem tests linear-time graph traversal, disconnected and isolated nodes, conflict detection, parallel edges, self-loops, and correctness on large sparse inputs.
Given an undirected graph with `n` nodes labeled `0` through `n - 1` and a list of
undirected `edges`, decide whether every node can be assigned one of two colors so that
the two endpoints of every edge get different colors. Return `true` when such an
assignment exists and `false` otherwise.
Implement `is_two_colorable(n, edges)`.
- `edges[i] = [u, v]` is an undirected edge joining node `u` and node `v`. The order
inside a pair carries no meaning: `[u, v]` and `[v, u]` are the same edge.
- The graph may be disconnected and may contain isolated nodes. Every connected
component is colored independently, and a component that uses only one of the two
colors is allowed, so an isolated node never makes the answer `false`.
- Parallel edges may appear (the same pair listed more than once, in either order) and
never change the answer.
- A self-loop (`u == v`) makes the answer `false`, because a node can never differ in
color from itself.
- `n = 0` with an empty edge list is a valid input, and the answer is `true`.
- The coloring itself is never returned, only whether one exists.
## Output
The answer is a single boolean: `true` when a valid two-coloring exists, `false`
otherwise. Exactly one boolean is correct for any input, so no ordering or
tie-breaking rule applies.
## Examples
**Example 1**
```text
n = 4, edges = [[0, 1], [1, 2], [2, 3], [3, 0]]
output = true
```
The cycle `0 - 1 - 2 - 3 - 0` has even length. Give nodes `0` and `2` the first color and
nodes `1` and `3` the second color; every one of the four edges then joins two different
colors.
**Example 2**
```text
n = 3, edges = [[0, 1], [1, 2], [2, 0]]
output = false
```
The triangle is an odd cycle. Coloring `0` first forces `1` to take the second color,
which forces `2` back to the first color, but `2` is also adjacent to `0`. Two colors
cannot satisfy all three edges, so the answer is `false`.
**Example 3**
```text
n = 5, edges = [[0, 1], [3, 4]]
output = true
```
The graph is disconnected: `{0, 1}` and `{3, 4}` are separate edges and node `2` is
isolated. Each component is colored on its own, and node `2` may take either color.
Constraints
- 0 <= n <= 200000
- 0 <= len(edges) <= 300000
- Every edge is a pair [u, v] with 0 <= u, v < n
- A self-loop (u == v) may appear in edges and makes the answer false
- Parallel edges may appear and do not change the answer
- The graph may be disconnected and may contain isolated nodes
- Every value in the input is a node label or a count, so nothing exceeds 199999: int in Java and int in C++ are sufficient, and no quantity comes near 2^53
- n can reach 200000 and the graph can be one long path, so a recursive depth-first coloring can exhaust the call stack; drive the traversal from an explicit stack or queue
- Target complexity: O(n + len(edges)) time and O(n + len(edges)) space
Examples
Input: (4, [[0, 1], [1, 2], [2, 3], [3, 0]])
Expected Output: True
Explanation: Worked Example 1. The 4-cycle has even length, so alternating the two colors around it succeeds.
Input: (3, [[0, 1], [1, 2], [2, 0]])
Expected Output: False
Explanation: Worked Example 2. The triangle is an odd cycle, so the two forced colors collide on the closing edge.
Hints
- Two-colorability is a property of each connected component on its own. A traversal that starts only at node 0 silently ignores whole components in a disconnected graph.
- Give the first node of a component either color, then decide what the traversal should do the first time it reaches a node versus the times it reaches one that already has a color.
- Think about which structure inside a component forces the two colors to collide, and notice what a self-loop is the degenerate case of.