提出 #4462059

---

ソースコード 拡げる

open Printf open Scanf
open Array

module UnionFind = struct
  let init n = Array.make n (-1)
  let is_root i a = a.(i) < 0
  let rec root_destructive x a =
    if a.(x) < 0 then x
    else (a.(x) <- root_destructive a.(x) a; a.(x))
  let size_destructive i a = let r = root_destructive i a in -a.(r)
  let same_destructive x y a = root_destructive x a = root_destructive y a
  let connect_destructive x y a =
    let p,q = root_destructive x a,root_destructive y a
    in if p = q then () else (
      let p,q = if a.(p) > a.(q) then q,p else p,q
      in
      a.(p) <- a.(p) + a.(q); a.(q) <- p)
end module UF = UnionFind
let rev a = a |> to_list |> List.rev |> of_list

let () = scanf " %d %d" @@ fun n m ->
  let uf = UF.init n in
  let q = rev @@
    init m (fun _ -> scanf " %d %d" @@ fun a b -> a-1,b-1)
  in
  let d = map (fun (a,b) ->
    if not @@ UF.same_destructive a b uf then (
      let p,q =
        UF.size_destructive a uf,
        UF.size_destructive b uf in
      UF.connect_destructive a b uf;
      p*q
    ) else 0
  ) q |> rev in
  ignore @@ fold_left (fun sum v ->
    let w = sum + v in
    printf "%d\n" w; w
  ) 0 d

提出情報

ジャッジ結果