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.