Split people who dislike each other

from collections import deque

def possible_bipartition(n, dislikes):
    adj = [[] for _ in range(n + 1)]     # people are 1..n
    for a, b in dislikes:
        adj[a].append(b)
        adj[b].append(a)
    room = [-1] * (n + 1)
    for s in range(1, n + 1):
        if room[s] != -1:
            continue
        room[s] = 0
        q = deque([s])
        while q:
            u = q.popleft()
            for v in adj[u]:
                if room[v] == -1:
                    room[v] = 1 - room[u]        # must be in the other room
                    q.append(v)
                elif room[v] == room[u]:
                    return False
    return True

#include <queue>
#include <vector>

bool solve(int n, const std::vector<std::vector<int>>& dislikes) {
    std::vector<std::vector<int>> adj(n + 1);                // people are 1..n
    for (const auto& d : dislikes) { adj[d[0]].push_back(d[1]); adj[d[1]].push_back(d[0]); }
    std::vector<int> room(n + 1, -1);
    for (int s = 1; s <= n; ++s) {
        if (room[s] != -1) continue;
        room[s] = 0;
        std::queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            for (int v : adj[u]) {
                if (room[v] == -1) { room[v] = 1 - room[u]; q.push(v); }   // the other room
                else if (room[v] == room[u]) return false;
            }
        }
    }
    return true;
}

import java.util.*;

class Solution {
    public boolean possibleBipartition(int n, int[][] dislikes) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i <= n; i++) adj.add(new ArrayList<>());   // people are 1..n
        for (int[] d : dislikes) { adj.get(d[0]).add(d[1]); adj.get(d[1]).add(d[0]); }
        int[] room = new int[n + 1];
        Arrays.fill(room, -1);
        for (int s = 1; s <= n; s++) {
            if (room[s] != -1) continue;
            room[s] = 0;
            ArrayDeque<Integer> q = new ArrayDeque<>();
            q.add(s);
            while (!q.isEmpty()) {
                int u = q.poll();
                for (int v : adj.get(u)) {
                    if (room[v] == -1) { room[v] = 1 - room[u]; q.add(v); }   // the other room
                    else if (room[v] == room[u]) return false;
                }
            }
        }
        return true;
    }
}

function possibleBipartition(n, dislikes) {
  const adj = Array.from({ length: n + 1 }, () => []);   // people are 1..n
  for (const [a, b] of dislikes) { adj[a].push(b); adj[b].push(a); }
  const room = new Array(n + 1).fill(-1);
  for (let s = 1; s <= n; s++) {
    if (room[s] !== -1) continue;
    room[s] = 0;
    const q = [s];
    for (let head = 0; head < q.length; head++) {
      const u = q[head];
      for (const v of adj[u]) {
        if (room[v] === -1) { room[v] = 1 - room[u]; q.push(v); }   // the other room
        else if (room[v] === room[u]) return false;
      }
    }
  }
  return true;
}

use std::collections::VecDeque;

fn solve(n: i64, dislikes: &[[i64; 2]]) -> bool {
    let n = n as usize;
    let mut adj = vec![Vec::new(); n + 1];                   // people are 1..n
    for d in dislikes {
        let (a, b) = (d[0] as usize, d[1] as usize);
        adj[a].push(b);
        adj[b].push(a);
    }
    let mut room = vec![-1i8; n + 1];
    for s in 1..=n {
        if room[s] != -1 {
            continue;
        }
        room[s] = 0;
        let mut q = VecDeque::from([s]);
        while let Some(u) = q.pop_front() {
            for &v in &adj[u] {
                if room[v] == -1 {
                    room[v] = 1 - room[u];                   // the other room
                    q.push_back(v);
                } else if room[v] == room[u] {
                    return false;
                }
            }
        }
    }
    true
}

import qualified Data.Map.Strict as M
import Data.Sequence (Seq (..), (|>))
import qualified Data.Sequence as Q

solve :: Int -> [[Int]] -> Bool
solve n dislikes = go [1 .. n] M.empty
  where
    adj = M.fromListWith (++) (concat [[(a, [b]), (b, [a])] | [a, b] <- dislikes])
    go [] _ = True
    go (s : rest) room
      | M.member s room = go rest room
      | otherwise = maybe False (go rest) (place (Q.singleton s) (M.insert s False room))
    -- breadth-first: everyone a person dislikes goes in the other room
    place Empty room = Just room
    place (u :<| q) room = step (M.findWithDefault [] u adj) q room
      where
        ru = room M.! u
        step [] q' r = place q' r
        step (v : vs) q' r = case M.lookup v r of
          Nothing -> step vs (q' |> v) (M.insert v (not ru) r)
          Just rv | rv == ru -> Nothing
                  | otherwise -> step vs q' r