kpdsu: 競技プログラミング向け Union-Find（Disjoint Set Union）

目的もくてき:

• 連結判定・連結成分併合を高速に処理する DSU を提供します。

実装じっそう:

• parent / size の 2 配列を持つハンドル構造です。
• find は経路圧縮、unite はサイズ併合を行います。

注意ちゅうい:

• 頂点番号は 0-index 前提です。

#entry main
#target std
#import "kp/kpdsu" as *
#import "std/stdio" as *
fn main <()*> ()> ():
    let d <i32> dsu_new 5;
    dsu_unite d 0 1;
    dsu_unite d 1 2;
    print_i32 if dsu_same d 0 2 then 1 else 0;
    print " ";
    print_i32 if dsu_same d 0 3 then 1 else 0;
    print " ";
    println_i32 dsu_size d 0;
    dsu_free d

1 0 3

dsu_new: n 頂点の DSU を作る
dsu_free: DSU の内部領域を解放する
dsu_find: 要素 x の代表元を返す
dsu_same: a と b が同じ連結成分か判定する
dsu_unite: a と b の成分を併合する（既に同じなら何もしない）
dsu_size: x が属する成分サイズを返す