Détecter un cycle

let a_cycle adj =
  let n = Array.length adj in
  let vu = Array.make n false in
  let rec visite s pere =
    vu.(s) <- true;
    let rec verifie voisins =
      match voisins with
      | [] -> false
      | v :: reste ->
          if not vu.(v) then visite v s || verifie reste
          else if v <> pere then true        (* déjà vu, <> père : cycle ! *)
          else verifie reste
    in
    verifie adj.(s)
  in
  let rec balaye s =
    if s = n then false
    else if not vu.(s) then visite s (-1) || balaye (s + 1)
    else balaye (s + 1)
  in
  balaye 0

On effectue un DFS en retenant le pere (le sommet d'où l'on vient). Rencontrer un voisin déjà vu qui n'est pas le père signale un cycle (on est revenu sur ses pas par un autre chemin). Le balaye relance sur chaque composante.