open Graph.Pack.Digraph

(* tarjan function *)
let tarjan g =
  let nb_of_vertex = nb_vertex g in
  let cfc = Array.create nb_of_vertex 0 in
  let nv = Array.create nb_of_vertex true in
  let ind = Array.create nb_of_vertex 0 in
  let ind_rec = Array.create nb_of_vertex 0 in
  let icfc = ref 1 in
  let i = ref 1 in
  let p = Stack.create () in

  (* function checks if element exists already in stack *)
  let exists stack element =
    try
      Stack.iter (fun x-> if x = element then raise Exit;) stack;
      false;
    with
    Exit -> true
      | _ -> false in

  (* function descente *)
  let rec descente s_ =
    let s = V.label s_ in
    Stack.push s p ;    (* we store numbers only in stack *)
    nv.(s) <- false ;   (* NV[s] <- faux *)
    ind.(s) <- !i ;     (* ind[s] <- i *)
    ind_rec.(s) <- !i ; (* ind_rac[s] <- i *)
    i := !i + 1 ;       (* i <- i +1 *)

    (* for all succeseurs *)
    iter_succ
      (fun x_ ->
    let x=(V.label x_) in
    if nv.(x) then
      begin
        descente x_;
        ind_rec.(s) <- (min ind_rec.(s) ind_rec.(x));
      end
    else
      if (exists p x) then
        ind_rec.(s) <- (min ind_rec.(s) ind.(x) );) g s_;

    if ind_rec.(s) = ind.(s) then

      let z = ref (Stack.pop p) in
      cfc.(!z) <- !icfc;

      while !z != s do
    z := Stack.pop p;
    cfc.(!z) <- !icfc;
      done;

      icfc := !icfc+1;
  in

  (* for all vertex if nv[x] then (descente x g) *)
  iter_vertex
    (fun x_ ->
      begin
    let x=(V.label x_) in
    if nv.(x) then
      descente x_;
      end) g;

  (* return cfc *)
  cfc
;;

let g = Rand.graph ~v:8 ~e:12 ();;
let k = tarjan g;;

let i = ref 0 in
while !i < 8 do
  print_endline ( (string_of_int !i)^ " " ^(string_of_int k.(!i)));
  i:= !i+1;
done;
display_with_gv g;