Cycles in an undirected graph

def has_cycle(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)
    seen = [False] * n
    for s in range(n):
        if seen[s]:
            continue
        seen[s] = True
        stack = [(s, -1)]                  # (node, the node it was reached from)
        while stack:
            u, parent = stack.pop()
            for v in adj[u]:
                if v == parent:
                    continue               # the edge we arrived on
                if seen[v]:
                    return True            # reached a second way: a cycle
                seen[v] = True
                stack.append((v, u))
    return False

#include <utility>
#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<bool> seen(n, false);
    for (int s = 0; s < n; ++s) {
        if (seen[s]) continue;
        seen[s] = true;
        std::vector<std::pair<int, int>> stack{{s, -1}};   // (node, parent)
        while (!stack.empty()) {
            auto [u, parent] = stack.back();
            stack.pop_back();
            for (int v : adj[u]) {
                if (v == parent) continue;                 // the edge we arrived on
                if (seen[v]) return true;                  // reached a second way
                seen[v] = true;
                stack.push_back({v, u});
            }
        }
    }
    return false;
}

import java.util.*;

class Solution {
    public boolean hasCycle(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]);
        }
        boolean[] seen = new boolean[n];
        ArrayDeque<int[]> stack = new ArrayDeque<>();
        for (int s = 0; s < n; s++) {
            if (seen[s]) continue;
            seen[s] = true;
            stack.push(new int[]{s, -1});                  // {node, parent}
            while (!stack.isEmpty()) {
                int[] top = stack.pop();
                int u = top[0], parent = top[1];
                for (int v : adj.get(u)) {
                    if (v == parent) continue;             // the edge we arrived on
                    if (seen[v]) return true;              // reached a second way
                    seen[v] = true;
                    stack.push(new int[]{v, u});
                }
            }
        }
        return false;
    }
}

function hasCycle(n, edges) {
  const adj = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) { adj[u].push(v); adj[v].push(u); }
  const seen = new Array(n).fill(false);
  for (let s = 0; s < n; s++) {
    if (seen[s]) continue;
    seen[s] = true;
    const stack = [[s, -1]];              // [node, the node it was reached from]
    while (stack.length) {
      const [u, parent] = stack.pop();
      for (const v of adj[u]) {
        if (v === parent) continue;       // the edge we arrived on
        if (seen[v]) return true;         // reached a second way: a cycle
        seen[v] = true;
        stack.push([v, u]);
      }
    }
  }
  return false;
}

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 (u, v) = (e[0] as usize, e[1] as usize);
        adj[u].push(v);
        adj[v].push(u);
    }
    let mut seen = vec![false; n];
    for s in 0..n {
        if seen[s] {
            continue;
        }
        seen[s] = true;
        let mut stack = vec![(s, usize::MAX)];          // (node, parent)
        while let Some((u, parent)) = stack.pop() {
            for &v in &adj[u] {
                if v == parent {
                    continue;                           // the edge we arrived on
                }
                if seen[v] {
                    return true;                        // reached a second way
                }
                seen[v] = true;
                stack.push((v, u));
            }
        }
    }
    false
}

import qualified Data.Map.Strict as M
import qualified Data.Set as S

solve :: Int -> [[Int]] -> Bool
solve n edges = go [0 .. n - 1] S.empty
  where
    adj = M.fromListWith (++) (concat [[(u, [v]), (v, [u])] | [u, v] <- edges])
    nbrs u = M.findWithDefault [] u adj
    -- start a search from every node not yet seen
    go [] _ = False
    go (s : rest) seen
      | S.member s seen = go rest seen
      | otherwise = case search [(s, -1)] (S.insert s seen) of
          Nothing -> True
          Just seen' -> go rest seen'
    -- Nothing means a cycle was found; Just carries the visited set on
    search [] seen = Just seen
    search ((u, parent) : stack) seen = step (nbrs u) stack seen
      where
        step [] st sn = search st sn
        step (v : vs) st sn
          | v == parent = step vs st sn
          | S.member v sn = Nothing
          | otherwise = step vs ((v, u) : st) (S.insert v sn)