CodeWithYash

Intermediate · Module 17 · Lesson 5

Cycle & bipartite detection

Use colors, parents, or recursion state.

15–25 min readLesson 99 of 123

Lesson 99 of 123

1d streak

Theory lesson · Step-by-step

Understand Cycle & bipartite detection

Use colors, parents, or recursion state.

Worked approach

Trace the reasoning step by step

  1. 1Choose a graph representation and define directedness and weights for Cycle & bipartite detection.
  2. 2Initialize visited, distance, parent, color, indegree, or component state.
  3. 3Remove one frontier item and inspect each outgoing edge.
  4. 4Update only when an edge proves new or better information.
  5. 5Repeat from every unvisited vertex when the graph may be disconnected.

Concrete example

Two-color triangle 0–1–2–0.

  1. 1Color 0 red and neighbors 1,2 blue.
  2. 2Edge 1–2 connects equal colors.

The triangle is not bipartite and contains an odd cycle.

What must remain true (Loop Invariant)

Every vertex finalized by Cycle & bipartite detection has the promised reachability, component, order, or distance property; frontier state represents discovered but unfinished work.

Cost Model

Complexity & Trade-offs

DFS / BFS coloring
O(V + E)
O(V)
The bound follows from the number of states visited and the work performed per transition.

When to use it

  • Networks, dependencies, connectivity, shortest paths, and grid movement.
  • Ordering prerequisite-constrained work.
  • Grouping reachable or mutually reachable states.

Common mistakes

  • Marking visited too late and enqueuing the same vertex repeatedly.
  • Ignoring disconnected components.
  • Using an algorithm whose weight assumptions do not match the graph.

Practice prompts

  • Reproduce the worked Cycle & bipartite detection example without looking at the trace.
  • Change one input condition and explain whether the Cycle & bipartite detection invariant still holds.
  • Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.
Explain why every transition is safe.
Construct a worst-case input.
Name one alternative and its trade-off.