807: Bipartite Graph Detection (2-Colouring)

Difficulty: 3 Level: Advanced Determine whether a graph can be 2-coloured — equivalent to detecting odd cycles — using BFS in O(V+E).

The Problem This Solves

A graph is bipartite if its vertices can be split into two sets such that every edge connects a vertex in one set to a vertex in the other — never two vertices in the same set. This is equivalent to asking: can you 2-colour the graph? And equivalently: does it contain any odd-length cycle? Bipartiteness appears in matching problems (job assignments, stable marriage), scheduling (tasks and machines), and database query optimization. Any time you have a "two-sided" relationship — users and items in a recommendation system, students and courses — you're working with a bipartite structure. Checking bipartiteness before running a matching algorithm saves you from applying algorithms that require it when the input violates the assumption. The algorithm returns either a valid 2-colouring (each vertex labelled 0 or 1) or a proof of non-bipartiteness via the odd cycle. Even for disconnected graphs, each component is checked independently.

The Intuition

BFS naturally enforces 2-colouring. Start at any vertex, colour it 0. Colour all its neighbours 1. Colour their unvisited neighbours 0. If you ever try to colour a vertex that already has the same colour as its neighbour, you've found an odd cycle — the graph is not bipartite. The assignment `color[w] = 1 - color[v]` is the entire logic: flip the colour at each BFS level. If a cross-edge connects two same-coloured vertices, the cycle length is even+1 = odd. O(V+E) time. This is one of the cleanest BFS applications: no visited array needed separately — uncoloured vertices serve as "unvisited." In OCaml, you'd use `Option` to represent uncoloured. In Rust, `i8` with -1 as sentinel is compact and cache-friendly.

How It Works in Rust

use std::collections::VecDeque;

fn is_bipartite(adj: &[Vec<usize>]) -> Option<Vec<i8>> {
 let n = adj.len();
 let mut color = vec![-1i8; n]; // -1 = uncoloured

 for start in 0..n {
     if color[start] != -1 { continue; } // already coloured

     // BFS from this component's root
     color[start] = 0;
     let mut queue = VecDeque::from([start]);

     while let Some(v) = queue.pop_front() {
         for &w in &adj[v] {
             if color[w] == -1 {
                 color[w] = 1 - color[v]; // flip colour
                 queue.push_back(w);
             } else if color[w] == color[v] {
                 return None; // same colour on both ends → odd cycle
             }
         }
     }
 }
 Some(color) // valid 2-colouring
}

`VecDeque` from the standard library is Rust's double-ended queue — the natural choice for BFS. `pop_front` is O(1) amortised. Using `i8` instead of an `Option<u8>` avoids the overhead of matching and keeps the color array tight in memory. The `1 - color[v]` trick works because colours are 0 and 1 — flipping between them with subtraction avoids a branch.

What This Unlocks

Maximum bipartite matching: König's theorem, Hopcroft-Karp, Hungarian algorithm — all require a bipartite graph as input.
Graph colouring lower bound: a graph that isn't bipartite requires at least 3 colours; bipartite graphs are exactly the 2-colourable ones.
Cycle parity in dependency graphs: detecting odd cycles in constraint graphs (e.g., in 2-SAT preprocessing or scheduling feasibility).

Key Differences

Concept	OCaml	Rust
Uncoloured sentinel	`None` in `int option array`	`-1i8` — avoids `Option` wrapping overhead
Queue	`Queue.t` module	`VecDeque<usize>` from `std::collections`
Colour flip	`1 - c` or `match c`	`1 - color[v]` — same idiom
Disconnected graph	Explicit loop over components	Same outer `for start in 0..n` loop
Early exit	`raise Exit` or `Result`	`return None` — idiomatic `Option` return

// Bipartite Check — BFS 2-colouring O(V+E)
use std::collections::VecDeque;

fn is_bipartite(adj: &[Vec<usize>]) -> Option<Vec<i8>> {
    let n = adj.len();
    let mut color = vec![-1i8; n];

    for start in 0..n {
        if color[start] != -1 { continue; }
        color[start] = 0;
        let mut deque = VecDeque::from([start]);
        while let Some(u) = deque.pop_front() {
            for &v in &adj[u] {
                if color[v] == -1 {
                    color[v] = 1 - color[u];
                    deque.push_back(v);
                } else if color[v] == color[u] {
                    return None; // odd cycle
                }
            }
        }
    }
    Some(color)
}

fn main() {
    // 4-cycle: bipartite
    let mut adj1 = vec![vec![]; 4];
    let mut add1 = |u: usize, v: usize| { adj1[u].push(v); adj1[v].push(u); };
    add1(0,1); add1(1,2); add1(2,3); add1(3,0);
    match is_bipartite(&adj1) {
        None    => println!("4-cycle: NOT bipartite"),
        Some(c) => println!("4-cycle: bipartite, colors={:?}", c),
    }

    // Triangle: not bipartite
    let mut adj2 = vec![vec![]; 3];
    let mut add2 = |u: usize, v: usize| { adj2[u].push(v); adj2[v].push(u); };
    add2(0,1); add2(1,2); add2(2,0);
    match is_bipartite(&adj2) {
        None    => println!("Triangle: NOT bipartite"),
        Some(c) => println!("Triangle: bipartite, colors={:?}", c),
    }

    // Complete bipartite K3,3
    let mut adj3 = vec![vec![]; 6];
    let mut add3 = |u: usize, v: usize| { adj3[u].push(v); adj3[v].push(u); };
    for u in 0..3 { for v in 3..6 { add3(u, v); } }
    match is_bipartite(&adj3) {
        None    => println!("K3,3: NOT bipartite"),
        Some(c) => println!("K3,3: bipartite, colors={:?}", c),
    }
}

(* Bipartite Check — BFS 2-colouring O(V+E) *)

let is_bipartite adj n =
  let color = Array.make n (-1) in
  let result = ref true in
  let q = Queue.create () in
  for start = 0 to n - 1 do
    if color.(start) = -1 && !result then begin
      color.(start) <- 0;
      Queue.push start q;
      while not (Queue.is_empty q) && !result do
        let u = Queue.pop q in
        List.iter (fun v ->
          if color.(v) = -1 then begin
            color.(v) <- 1 - color.(u);
            Queue.push v q
          end else if color.(v) = color.(u) then
            result := false
        ) adj.(u)
      done
    end
  done;
  if !result then Some color else None

let () =
  let n1  = 4 in
  let adj1 = Array.make n1 [] in
  let add1 u v = adj1.(u) <- v :: adj1.(u); adj1.(v) <- u :: adj1.(v) in
  add1 0 1; add1 1 2; add1 2 3; add1 3 0;  (* 4-cycle — bipartite *)
  (match is_bipartite adj1 n1 with
   | None   -> Printf.printf "4-cycle: NOT bipartite\n"
   | Some c -> Printf.printf "4-cycle: bipartite, colors=[%s]\n"
       (String.concat "," (Array.to_list (Array.map string_of_int c))));

  let n2   = 3 in
  let adj2 = Array.make n2 [] in
  let add2 u v = adj2.(u) <- v :: adj2.(u); adj2.(v) <- u :: adj2.(v) in
  add2 0 1; add2 1 2; add2 2 0;  (* triangle — not bipartite *)
  (match is_bipartite adj2 n2 with
   | None   -> Printf.printf "Triangle: NOT bipartite\n"
   | Some c -> Printf.printf "Triangle: bipartite, colors=[%s]\n"
       (String.concat "," (Array.to_list (Array.map string_of_int c))))