Kody 2

(*Zadania z kolokwiów*)
(*1 III13/14*)
(*Postiadamu globalnie zadeklarowany graph g*)
let path () =
  let n = size g in
  let length = Array.make n 0 in
  let look akt l =
    List.fold_left (fun wyn node ->
      if akt < node then max (length.(node)+1) wyn
      else wyn) 0 l in

  let wynik = ref 0 in

  for i = (n-1) downto 0 do
    let l = neighbours g i in
    wynik:= look i l;
    length.(i) <- !wynik
done;
!wynik;;
(* Kolokwium 2017/18 *)
open Array;;
let segment t =
    let n = Array.length t in
    let dp = make_matrix n n 0 in
    let fib = make (n + 1) 0 in
    fib.(1) <- 1; fib.(2) <- 1;
    let i = ref 3 in
    while !i <= n
    do
        fib.(!i) <- fib.(!i - 1) + fib.(!i - 2); i := !i + 1;
    done;
    i := 0; let j = ref 0 in
    while !i < n
    do
        j := 2;
        while !j <= n
        do
            if t.(!i) = fib.(!j) then dp.(!i).(!i) <- !j;
            j := !j + 1;
        done;
        i := !i + 1;
    done;
    let odp = ref 0 in
    i := 1;
    while !i < n
    do
        j := 0;
        while !i + !j < n
        do
            let l = ref !j in
            while !l < !i + !j
            do
                let a = dp.(!j).(!l) and b = dp.(!l + 1).(!j + !i) in
                if a = 2 && b = 2
                then dp.(!j).(!j + !i) <- 3
                else if a - b = 1 || a - b = -1
                then dp.(!j).(!j + !i) <- max a b + 1;
                l := !l + 1;
            done;
            odp := max !odp dp.(!j).(!j + !i);
            j := !j + 1;
        done;
        i := !i + 1;
    done;
    !odp;;

(*segment [|4; 2; 1; 2; 3; 5; 2; 8; 7|];;*)

(* sadzawka [| [|2; 3; 2|]; [|2; 1; 2|]; [|2; 2; 2|] |] (1, 1) *)

let sadzawka sadz (x, y) =
    let xsize = Array.length sadz in
    let ysize = Array.length sadz.(0) in
    let rozmiar = xsize * ysize in
    let kolejka = make (rozmiar + 1) [] in
    let i = ref 0 and j = ref 0 in
    while !i < xsize
    do
        while !j < ysize
        do
            let pole = sadz.(!i).(!j) in
            kolejka.(pole) <- ((!i, !j)::kolejka.(pole));
            j := !j + 1;
        done;
        i := !i + 1;
    done;
    let lider = init (rozmiar + 1) (fun x -> x) in
    let rec f a =
        if lider.(a) = a then a
            else begin lider.(a) <- f lider.(a); lider.(a) end
    in
    let union a b =
        if f b = rozmiar then lider.(f a) <- f b
            else lider.(f b) <- f a
    in
    i := rozmiar;
    let jest = ref false in
    while !jest = false && !i > 0
    do
        let rec dod lis =
            match lis with
            | [] -> ()
            | (ax, ay)::t ->
                if ax = 0 || ax = xsize - 1 || ay = 0 || ay = ysize - 1 then
                    union rozmiar (ax * ysize + ay);
                if ax > 0 then union ((ax - 1) * ysize + ay) (ax * ysize + ay);
                if ax < xsize - 1 then union ((ax + 1) * ysize + ay) (ax * ysize + ay);
                if ay > 0 then union (ax * ysize + ay - 1) (ax * ysize + ay);
                if ay < ysize - 1 then union (ax * ysize + ay + 1) (ax * ysize +ay);
                dod t
            in
            dod kolejka.(!i);
            if f (x * ysize + y) = rozmiar && sadz.(x).(y) >= !i then jest := true;
            i := !i - 1;
    done;
    !i + 2;;