Depth-first order of a graph

def dfs_order(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)            # undirected: store both directions
    for nb in adj:
        nb.sort()                   # smallest neighbour first
    seen = [False] * n
    order = []

    def dfs(u):
        seen[u] = True              # mark on entry
        order.append(u)
        for v in adj[u]:
            if not seen[v]:
                dfs(v)

    for s in range(n):              # one search per unvisited part
        if not seen[s]:
            dfs(s)
    return order

#include <algorithm>
#include <functional>
#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]);          // undirected: store both directions
    }
    for (auto& nb : adj) std::sort(nb.begin(), nb.end());
    std::vector<bool> seen(n, false);
    std::vector<int> order;
    std::function<void(int)> dfs = [&](int u) {
        seen[u] = true;                     // mark on entry
        order.push_back(u);
        for (int v : adj[u]) if (!seen[v]) dfs(v);
    };
    for (int s = 0; s < n; ++s) if (!seen[s]) dfs(s);
    return order;
}

import java.util.*;

class Solution {
    private List<List<Integer>> adj;
    private boolean[] seen;
    private int[] order;
    private int count;

    public int[] dfsOrder(int n, int[][] edges) {
        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]);            // undirected: store both directions
        }
        for (List<Integer> nb : adj) Collections.sort(nb);
        seen = new boolean[n];
        order = new int[n];
        count = 0;
        for (int s = 0; s < n; s++) if (!seen[s]) dfs(s);
        return order;
    }

    private void dfs(int u) {
        seen[u] = true;                         // mark on entry
        order[count++] = u;
        for (int v : adj.get(u)) if (!seen[v]) dfs(v);
    }
}

function dfsOrder(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    adj[u].push(v);
    adj[v].push(u);                // undirected: store both directions
  }
  for (const nb of adj) nb.sort((a, b) => a - b);
  const seen = new Array(n).fill(false);
  const order = [];
  const dfs = u => {
    seen[u] = true;                // mark on entry
    order.push(u);
    for (const v of adj[u]) if (!seen[v]) dfs(v);
  };
  for (let s = 0; s < n; s++) if (!seen[s]) dfs(s);
  return order;
}

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);                         // undirected: store both directions
    }
    for nb in adj.iter_mut() {
        nb.sort();
    }
    fn dfs(u: usize, adj: &[Vec<usize>], seen: &mut Vec<bool>, order: &mut Vec<i64>) {
        seen[u] = true;                         // mark on entry
        order.push(u as i64);
        for &v in &adj[u] {
            if !seen[v] {
                dfs(v, adj, seen, order);
            }
        }
    }
    let mut seen = vec![false; n];
    let mut order = Vec::with_capacity(n);
    for s in 0..n {
        if !seen[s] {
            dfs(s, &adj, &mut seen, &mut order);
        }
    }
    order
}

import Data.List (foldl', sort)
import qualified Data.Map.Strict as M
import qualified Data.Set as S

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]))
    -- the state is (visited set, visit order reversed)
    start acc@(seen, _) s
      | S.member s seen = acc
      | otherwise = dfs acc s
    dfs (seen, order) u = foldl' visit (S.insert u seen, u : order) (M.findWithDefault [] u adj)
    visit acc@(seen, _) v
      | S.member v seen = acc
      | otherwise = dfs acc v