Algorithm1 Practice1 Interview

Bipartite Check

GuideCode Labs

Two-color graph components with BFS or DFS and reject edges joining equal colors. Learn the algorithm's preconditions, state transition, correctness argument, Python cost model, and transfer from one focused drill to a full Interview Problem.

Recognize it when

Consider Bipartite Check when the prompt's constraints and required operations match this shape: Two-color graph components with BFS or DFS and reject edges joining equal colors.

On this page · Assign Opposite Colors Across Edges

Checking your account…

Assign Opposite Colors Across Edges

A graph is bipartite exactly when vertices can receive two colors so every edge joins opposite colors. BFS or DFS propagates the forced opposite color.

Start Every Disconnected Component

An uncolored vertex seeds a new component with either color. Checking only one source can miss an odd cycle elsewhere in the graph.

Trace Bipartite Coloring

Reference

from collections import deque

def coloring_trace(adjacency):
    colors=[-1]*len(adjacency);trace=[]
    for start in range(len(adjacency)):
        if colors[start]!=-1:continue
        colors[start]=0;trace.append([start,0]);queue=deque([start])
        while queue:
            node=queue.popleft()
            for neighbor in adjacency[node]:
                if colors[neighbor]==-1:colors[neighbor]=1-colors[node];trace.append([neighbor,colors[neighbor]]);queue.append(neighbor)
    return trace

Practice

Implement coloring_trace(adjacency). Return [node,color] in BFS assignment order across all components, colors 0 and 1.

def coloring_trace(adjacency):
    pass

Public tests

Seed every disconnected component

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Reject Same Color Neighbors

For each edge, assign an unseen neighbor the opposite color or reject an already colored neighbor that matches the current color. A self-loop immediately violates the condition.

Check Bipartite Graph

Reference

from collections import deque

def is_bipartite(adjacency):
    colors=[-1]*len(adjacency)
    for start in range(len(adjacency)):
        if colors[start]!=-1:continue
        colors[start]=0;queue=deque([start])
        while queue:
            node=queue.popleft()
            for neighbor in adjacency[node]:
                if colors[neighbor]==-1:colors[neighbor]=1-colors[node];queue.append(neighbor)
                elif colors[neighbor]==colors[node]:return False
    return True

Practice

Implement is_bipartite(adjacency). Return whether every edge connects opposite colors across all components.

def is_bipartite(adjacency):
    pass

Public tests

Reject odd cycles and self loops

Loading interactive editor.If it does not appear, the reference and starter code remain readable.Reload editor

Recover the Odd Cycle Meaning

A same-color edge connects vertices at equal parity from the component seed, closing an odd-length cycle. Parent tracking can reconstruct that witness when the prompt requires more than a Boolean.

Explain It in an Interview

Say: “Color represents path-length parity from a component seed. Every edge must flip parity; a same-color edge proves an odd cycle.” State disconnected traversal and O(V + E) time and space.

Python Version Note

Python 3.11+

The code uses standard Python syntax and containers supported by the browser Judge. The Bipartite Check proof does not depend on a minor Python release.

Verify in Python docs

Complexity & Invariants

Interview bounds depend on the stated representation, input model, and real Python operations.

Operation	Average	Worst	Interview note
Bipartite Check complete workflow	`O(V + E)`	`O(V + E)`	Breadth-first color each component, assigning opposite colors across every edge.

Space

O(V + E) for the focused Validate a Bipartite Graph implementation.

Assumptions

Each discovered edge enforces opposite endpoint colors. A conflict proves an odd cycle; if all edges satisfy the rule, the two color classes form a valid bipartition.
The bound counts Python sorting, slicing, hashing, heap, recursion, and container-copy costs rather than treating syntax as free.

Invariants Worth Saying Aloud

State the precise Bipartite Check invariant before coding and preserve it after every update, traversal step, or recursive return.
Each visited marker or color has one direction-aware meaning.
A detected conflict corresponds to a real edge or repeated path state in the input.
Assign an opposite color when a node is first discovered. Preserve this claim after every transition.
Reject an edge whose endpoints share a color. Preserve this claim after every transition.

When To Use Or Avoid Bipartite Check

Use It When

Use Bipartite Check when this precondition is stated or can be proved: The representation and direction determine whether colors, indegrees, union-find, or fast-slow pointers are valid.
Use it when this maintained state removes repeated work: Each visited marker or color has one direction-aware meaning.

Choose Another Tool When

Avoid Bipartite Check when this precondition is absent: The representation and direction determine whether colors, indegrees, union-find, or fast-slow pointers are valid.
Avoid it when a simpler direct scan satisfies the constraints with less implementation risk.

Common Pitfalls

These are the mistakes most likely to survive a happy-path example and fail a boundary case.

Applying the algorithm without its precondition

Verify algorithm preconditions such as sorted input, nonnegative weights, acyclicity, or admissible heuristics before applying it.

Prevent it: State and verify this precondition before coding: The representation and direction determine whether colors, indegrees, union-find, or fast-slow pointers are valid.

Avoid

def is_bipartite(node_count, edges):
    pass

Use instead

def is_bipartite(node_count, edges):
    from collections import deque
    graph = [[] for _ in range(node_count)]
    for left, right in edges:
        graph[left].append(right); graph[right].append(left)
    colors = [-1] * node_count
    for start in range(node_count):
        if colors[start] != -1:
            continue
        colors[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if colors[neighbor] == -1:
                    colors[neighbor] = 1 - colors[node]; queue.append(neighbor)
                elif colors[neighbor] == colors[node]:
                    return False
    return True

Where you will hit this: Validate a Bipartite Graph(opens in a new tab)

Breaking the state transition

Always accepts and misses an odd cycle.

Prevent it: Preserve this proof obligation: The tracked state distinguishes an active revisit or incompatible edge from a harmless completed revisit.

Avoid

def is_bipartite(node_count,edges):
    return True

Use instead

def is_bipartite(node_count, edges):
    from collections import deque
    graph = [[] for _ in range(node_count)]
    for left, right in edges:
        graph[left].append(right); graph[right].append(left)
    colors = [-1] * node_count
    for start in range(node_count):
        if colors[start] != -1:
            continue
        colors[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if colors[neighbor] == -1:
                    colors[neighbor] = 1 - colors[node]; queue.append(neighbor)
                elif colors[neighbor] == colors[node]:
                    return False
    return True

Where you will hit this: Validate a Bipartite Graph(opens in a new tab)

Hiding Python work in the claimed bound

Include visited state, boundary cases, recursion depth, and hidden copying costs in correctness and complexity analysis.

Prevent it: Count every sort, slice, copy, membership check, heap update, and recursive frame before claiming O(V + E).

Avoid

def is_bipartite(node_count,edges):
    return True

Use instead

def is_bipartite(node_count, edges):
    from collections import deque
    graph = [[] for _ in range(node_count)]
    for left, right in edges:
        graph[left].append(right); graph[right].append(left)
    colors = [-1] * node_count
    for start in range(node_count):
        if colors[start] != -1:
            continue
        colors[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for neighbor in graph[node]:
                if colors[neighbor] == -1:
                    colors[neighbor] = 1 - colors[node]; queue.append(neighbor)
                elif colors[neighbor] == colors[node]:
                    return False
    return True

Where you will hit this: Lowest Common Ancestor in a BST(opens in a new tab)

Reviewed References

Official Python documentation supports language behavior. Canonical problem pages provide additional practice context.

Python More on Lists(opens in a new tab)
python-docs · checked 2026-07-27
Python collections.deque(opens in a new tab)
python-docs · checked 2026-07-12

Checking your account…

Bipartite Check Code Labs

Assign Opposite Colors Across Edges

Start Every Disconnected Component

Public tests

Reject Same Color Neighbors

Public tests

Recover the Odd Cycle Meaning

Explain It in an Interview

Python Version Note

Complexity & Invariants

Space

Assumptions

Invariants Worth Saying Aloud

When To Use Or Avoid Bipartite Check

Use It When

Choose Another Tool When

Common Pitfalls

Applying the algorithm without its precondition

Breaking the state transition

Hiding Python work in the claimed bound

Related Practice

Related Interview Problems

Reviewed References