Breadth-first order of a graph

from collections import deque

def bfs_order(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    for nb in adj:
        nb.sort()
    seen = [False] * n
    order = []
    for s in range(n):
        if seen[s]:
            continue
        seen[s] = True
        q = deque([s])
        while q:
            u = q.popleft()
            order.append(u)
            for v in adj[u]:
                if not seen[v]:
                    seen[v] = True      # mark on enqueue, so v is queued once
                    q.append(v)
    return order

#include <algorithm>
#include <queue>
#include <vector>

std::vector<int> 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]);
    }
    for (auto& nb : adj) std::sort(nb.begin(), nb.end());
    std::vector<bool> seen(n, false);
    std::vector<int> order;
    for (int s = 0; s < n; ++s) {
        if (seen[s]) continue;
        seen[s] = true;
        std::queue<int> q;
        q.push(s);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            order.push_back(u);
            for (int v : adj[u])
                if (!seen[v]) { seen[v] = true; q.push(v); }   // mark on enqueue
        }
    }
    return order;
}

import java.util.*;

class Solution {
    public int[] bfsOrder(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]);
        }
        for (List<Integer> nb : adj) Collections.sort(nb);
        boolean[] seen = new boolean[n];
        int[] order = new int[n];
        int count = 0;
        ArrayDeque<Integer> q = new ArrayDeque<>();
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            seen[s] = true;
            q.add(s);
            while (!q.isEmpty()) {
                int u = q.poll();
                order[count++] = u;
                for (int v : adj.get(u))
                    if (!seen[v]) { seen[v] = true; q.add(v); }   // mark on enqueue
            }
        }
        return order;
    }
}

function bfsOrder(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
  for (const nb of adj) nb.sort((a, b) => a - b);
  const seen = new Array(n).fill(false);
  const order = [];
  const q = new Array(n);
  let head = 0, tail = 0;            // an array used as a queue: O(1) at both ends
  for (let s = 0; s < n; s++) {
    if (seen[s]) continue;
    seen[s] = true;
    q[tail++] = s;
    while (head < tail) {
      const u = q[head++];
      order.push(u);
      for (const v of adj[u]) {
        if (!seen[v]) { seen[v] = true; q[tail++] = v; }   // mark on enqueue
      }
    }
  }
  return order;
}

use std::collections::VecDeque;

fn solve(n: i64, edges: &[[i64; 2]]) -> Vec<i64> {
    let n = n as usize;
    let mut adj = vec![Vec::new(); n];
    for e in edges {
        let (u, v) = (e[0] as usize, e[1] as usize);
        adj[u].push(v);
        adj[v].push(u);
    }
    for nb in adj.iter_mut() {
        nb.sort();
    }
    let mut seen = vec![false; n];
    let mut order = Vec::with_capacity(n);
    let mut q = VecDeque::new();
    for s in 0..n {
        if seen[s] {
            continue;
        }
        seen[s] = true;
        q.push_back(s);
        while let Some(u) = q.pop_front() {
            order.push(u as i64);
            for &v in &adj[u] {
                if !seen[v] {
                    seen[v] = true;                     // mark on enqueue
                    q.push_back(v);
                }
            }
        }
    }
    order
}

import Data.List (foldl', sort)
import qualified Data.Map.Strict as M
import qualified Data.Set as S
import Data.Sequence (Seq (..), (|>))
import qualified Data.Sequence as Q

solve :: Int -> [[Int]] -> [Int]
solve n edges = reverse (snd (foldl' start (S.empty, []) [0 .. n - 1]))
  where
    adj = M.map sort (M.fromListWith (++) (concat [[(u, [v]), (v, [u])] | [u, v] <- edges]))
    start acc@(seen, order) s
      | S.member s seen = acc
      | otherwise = bfs (Q.singleton s) (S.insert s seen) order
    -- the queue is a Data.Sequence: O(1) at both ends
    bfs Empty seen order = (seen, order)
    bfs (u :<| rest) seen order =
      let fresh = [v | v <- M.findWithDefault [] u adj, not (S.member v seen)]
          seen' = foldl' (flip S.insert) seen fresh          -- mark on enqueue
      in bfs (foldl' (|>) rest fresh) seen' (u : order)