Two-Coloring Graph (Bipartite): quick checklist + a pitfall

Checklist:
- Treat it as bipartite check. Use BFS/DFS to color 0/1.
- Handle disconnected graphs: start from every uncolored node.
- Self-loop → immediately not bipartite. Parallel edges are fine.
- Watch recursion depth; iterative BFS is safer for large graphs.
- Complexity: O(V + E), space O(V).

Tiny BFS template (Python):

python

from collections import deque, defaultdict

def is_bipartite(n, edges):
    g = defaultdict(list)
    for u, v in edges:
        if u == v:  # self-loop
            return False
        g[u].append(v)
        g[v].append(u)

    color = {}
    for start in range(n):
        if start in color:
            continue
        q = deque([start])
        color[start] = 0
        while q:
            u = q.popleft()
            for v in g[u]:
                if v not in color:
                    color[v] = color[u] ^ 1
                    q.append(v)
                elif color[v] == color[u]:
                    return False
    return True

If you need to explain “why not bipartite,” track parents and reconstruct the odd cycle when you detect the same-color edge.

Alternative worth knowing: DSU with parity (union-find with a 0/1 bit) is great when edges stream in and you want early conflict detection.

Anyone hit constraints on AlgoDaily’s version that force iterative only or 1-based node labels?

Team AlgoDaily Commented on Jul 20, 2025:

Sarah’s checklist mirrors how we grade this one.

AlgoDaily constraints don’t force iterative only, but in Python a deep DFS can hit RecursionError, so BFS or an explicit stack is the safer default.
Node labels in our prompt are 0-based. You don’t need to handle 1-based unless you’re pulling from external sources; if you are, normalize on read (u -= 1; v -= 1).
Parallel edges are fine; self-loops should fail immediately as you noted.
Disconnected graphs are in the tests.

Minor tweaks:
- Using a list for color (size n, init to -1) is a bit faster than a dict for Python.
- If edges might reference nodes not in [0, n-1], either validate or compute n = max_label + 1; our official inputs won’t do this, but it’s a common pitfall elsewhere.
- For “why not bipartite,” track parent and the BFS depth; when you hit a same-color edge u–v, climb parents to the LCA and output the odd cycle.

DSU with parity is accepted as a correct approach and is great for streaming edges.

Kind of like “Power of Three,” most wrong answers here come from tiny edge cases—self-loops and disconnected components—so your checklist covers the big ones.