(**************************************************************************)
(*                                                                        *)
(*  Thibaut Balabonski, Sylvain Conchon, Jean-Christophe Filliâtre,       *)
(*  Kim Nguyen, Laurent Sartre                                            *)
(*                                                                        *)
(*  Informatique - MP2I/MPI - CPGE 1re et 2e années.                      *)
(*  Cours et exercices corrigés. Éditions Ellipses, 2022.                 *)
(*                                                                        *)
(*  https://www.informatique-mpi.fr/                                      *)
(*                                                                        *)
(**************************************************************************)

(* Graphes non orientés par listes d'adjacence *)

include Digraph

type graph = digraph

let add_edge g u v =
  add_edge g u v;
  add_edge g v u

let edges g =
  let l = ref [] in
  for i = 0 to size g - 1 do
    List.iter (fun j -> if j > i then l := (i, j) :: !l) (succ g i)
  done;
  !l

let digraph g =
  g

(* Attention : on doit dupliquer load (car add_edge a changé)
   et print (pour ne pas afficher les arcs deux fois) *)

open Scanf

let load file =
  let c = Scanning.open_in file in
  let n = bscanf c "%d\n" (fun n -> n) in
  let g = create n in
  let e = bscanf c "%d\n" (fun e -> e) in
  for _ = 1 to e do bscanf c "%d %d\n" (add_edge g) done;
  g

open Format

let print fmt g =
  fprintf fmt "%d@\n" (size g);
  let e = edges g in
  fprintf fmt "%d@\n" (List.length e);
  List.iter (fun (i, j) -> fprintf fmt "%d %d@\n" i j) e

let has_cycle g s =
  let visited = Array.make (size g) false in
  let rec dfs u v =
    List.iter
      (fun w -> if visited.(w) then (if w <> u then raise Exit)
                else (visited.(w) <- true; dfs v w))
      (succ g v) in
  visited.(s) <- true;
  try dfs (-1) s; false with Exit -> true

(* exercice *)
let is_spanning_tree g el =
  let rec check uf = function
    | [] -> true
    | (u,v) :: el ->
        Union_find.find uf u <> Union_find.find uf v &&
        (Union_find.union uf u v; check uf el) in
  let n = size g in
  List.compare_length_with el (n - 1) = 0 &&
  check (Union_find.create n) el

(* exercice *)
let is_bipartite g =
  let n = size g in
  let color = Array.make n (-1) in
  let rec dfs c v = (* on vient de la couleur c *)
    if color.(v) = -1 then (
      color.(v) <- 1 - c;
      List.iter (dfs (1 - c)) (succ g v)
    ) else
      if color.(v) = c then raise Exit
  in
  try for i = 0 to n - 1 do if color.(i) = -1 then dfs 0 i done; true
  with Exit -> false

(* exercice *)
let is_matching g el =
  let free = Array.make (size g) true in
  let add (u, v) =
    free.(u) && free.(v) &&
    (free.(u) <- false; free.(v) <- false; true) in
  List.for_all add el

(* Quelques graphes particuliers.

   Attention : On doit dupliquer ce code de Digraph, car add_edge a changé. *)

let cycle n =
  let g = create n in
  for i = 0 to n-1 do add_edge g i ((i+1) mod n) done;
  g

let full ?(loop=false) n =
  let g = create n in
  for i = 0 to n-1 do
    for j = i to n-1 do
      if i <> j || loop then add_edge g i j
    done
  done;
  g

(* grille n*m où le sommet (i,j) est l'entier i*m+j *)
let grid n m =
  let g = create (n * m) in
  let v i j = i * m + j in
  for i = 0 to n-1 do
    for j = 0 to m-1 do
      if j < m-1 then add_edge g (v i j) (v i (j+1));
      if i < n-1 then add_edge g (v i j) (v (i+1) j)
    done
  done;
  g