Can the graph be split in two?

from collections import deque

def is_bipartite(n, edges):
    adj = [[] for _ in range(n)]
    for a, b in edges:
        adj[a].append(b)
        adj[b].append(a)
    colour = [-1] * n                    # -1 uncoloured, otherwise 0 or 1
    for s in range(n):
        if colour[s] != -1:
            continue
        colour[s] = 0                    # a new piece: its first node is free
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if colour[v] == -1:
                    colour[v] = 1 - colour[u]   # forced
                    q.append(v)
                elif colour[v] == colour[u]:
                    return False         # an edge inside one colour: odd cycle
    return True

#include <queue>
#include <vector>

bool solve(int n, const std::vector<std::vector<int>>& edges) {
    std::vector<std::vector<int>> adj(n);
    for (const auto& e : edges) { adj[e[0]].push_back(e[1]); adj[e[1]].push_back(e[0]); }
    std::vector<int> colour(n, -1);
    for (int s = 0; s < n; ++s) {
        if (colour[s] != -1) continue;
        colour[s] = 0;
        std::queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                if (colour[v] == -1) { colour[v] = 1 - colour[u]; q.push(v); }   // forced
                else if (colour[v] == colour[u]) return false;                    // odd cycle
            }
        }
    }
    return true;
}

import java.util.*;

class Solution {
    public boolean isBipartite(int n, int[][] edges) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] e : edges) { adj.get(e[0]).add(e[1]); adj.get(e[1]).add(e[0]); }
        int[] colour = new int[n];
        Arrays.fill(colour, -1);
        for (int s = 0; s < n; s++) {
            if (colour[s] != -1) continue;
            colour[s] = 0;
            ArrayDeque<Integer> q = new ArrayDeque<>();
            q.add(s);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj.get(u)) {
                    if (colour[v] == -1) { colour[v] = 1 - colour[u]; q.add(v); }   // forced
                    else if (colour[v] == colour[u]) return false;                   // odd cycle
                }
            }
        }
        return true;
    }
}

function isBipartite(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [a, b] of edges) { adj[a].push(b); adj[b].push(a); }
  const colour = new Array(n).fill(-1);
  for (let s = 0; s < n; s++) {
    if (colour[s] !== -1) continue;
    colour[s] = 0;
    const q = [s];
    for (let head = 0; head < q.length; head++) {
      const u = q[head];
      for (const v of adj[u]) {
        if (colour[v] === -1) { colour[v] = 1 - colour[u]; q.push(v); }   // forced colour
        else if (colour[v] === colour[u]) return false;                      // odd cycle
      }
    }
  }
  return true;
}

use std::collections::VecDeque;

fn solve(n: i64, edges: &[[i64; 2]]) -> bool {
    let n = n as usize;
    let mut adj = vec![Vec::new(); n];
    for e in edges {
        let (a, b) = (e[0] as usize, e[1] as usize);
        adj[a].push(b);
        adj[b].push(a);
    }
    let mut colour: Vec<Option<u8>> = vec![None; n];
    for s in 0..n {
        if colour[s].is_some() {
            continue;
        }
        colour[s] = Some(0);
        let mut q = VecDeque::from([s]);
        while let Some(u) = q.pop_front() {
            let cu = colour[u].unwrap();
            for &v in &adj[u] {
                match colour[v] {
                    None => {
                        colour[v] = Some(1 - cu);                // forced
                        q.push_back(v);
                    }
                    Some(cv) if cv == cu => return false,        // odd cycle
                    _ => {}
                }
            }
        }
    }
    true
}

import qualified Data.Map.Strict as M

solve :: Int -> [[Int]] -> Bool
solve n edges = go [0 .. n - 1] M.empty
  where
    adj = M.fromListWith (++) (concat [[(a, [b]), (b, [a])] | [a, b] <- edges])
    go [] _ = True
    go (s : rest) col
      | M.member s col = go rest col
      | otherwise = case paint [s] (M.insert s False col) of
          Nothing -> False
          Just col' -> go rest col'
    -- breadth-first colouring; Nothing as soon as an edge joins equal colours
    paint [] col = Just col
    paint (u : q) col = step (M.findWithDefault [] u adj) q col
      where
        cu = col M.! u
        step [] q' c = paint q' c
        step (v : vs) q' c = case M.lookup v c of
          Nothing -> step vs (q' ++ [v]) (M.insert v (not cu) c)
          Just cv | cv == cu -> Nothing
                  | otherwise -> step vs q' c