kpgraph: 競技プログラミング向けグラフ補助ライブラリ

目的もくてき:

• 小〜中規模入力で使いやすい密行列表現のグラフ API を提供します。
• 無向グラフの BFS 距離計算を定型化し、解法実装を短くします。

実装じっそう:

• 辺は n*n の u8 行列（0/1）で保持します。
• BFS は配列キュー（head/tail）で実装し、距離は -1 を未訪問として管理します。

注意ちゅうい:

• メモリ使用量は O(n^2) です。大規模グラフには不向きです。
• 頂点番号は 0-index を前提にしています。

#entry main
#target std
#import "std/streamio" as *
#import "std/iotarget" as *
#import "kp/kpgraph" as *
#import "alloc/collections/vec" as *
#import "core/field" as *
#import "core/mem" as *
fn main <()*> ()> ():
    let sc <StreamScanner> unwrap_ok open ReadStream::Stdio;
    let g <DenseGraph> dense_graph_read_undirected_1indexed sc;
    let n <i32> get g "n";
    let mat <i32> get g "mat";
    let dist <Vec<i32>> dense_graph_bfs_dist_raw n mat 0;

    let data <i32> mem_ptr_addr get dist "data";
    let mut w <StreamWriter> unwrap_ok open WriteStream::Stdio;
    let mut i <i32> 0;
    while lt i n:
        do:
            if lt 0 i:
                then set w write w " "
                else ()
            set w write w load_i32 add data mul i 4;
            set i add i 1;
    set w write w "\n";
    set w flush w;
    close w;
    close sc;

    dense_graph_free g

4 3
1 2
2 3
3 4

0 1 2 3

DenseGraph: 密行列表現の無向グラフ

目的もくてき:

• 頂点数 n と辺行列 mat をまとめて管理します。

実装じっそう:

• mat は長さ n*n の u8 配列（0: 辺なし, 1: 辺あり）です。

dense_graph_new: 頂点数 n の空グラフを作る

計算量けいさんりょう:

• O(n^2)

dense_graph_free: グラフの内部メモリを解放する

計算量けいさんりょう:

• O(1)

dense_graph_add_undirected: 無向辺 (u,v) を追加する

注意ちゅうい:

• 0-index の頂点番号を前提にします。

計算量けいさんりょう:

• O(1)

dense_graph_read_undirected_1indexed: 1-index 入力の無向グラフを読む

[入力形式]:

• n m
• u1 v1
• ...
• um vm

注意ちゅうい:

• 入力は 1-index を想定し、内部では 0-index に変換します。

計算量けいさんりょう:

• O(n^2 + m)

dense_graph_bfs_dist_raw: 開始頂点からの最短距離配列を返す

目的もくてき:

• 辺重み 1 のグラフで、開始頂点 start から各頂点への最短距離を計算します。

実装じっそう:

• 配列キューを使う通常の BFS です。
• 未訪問は -1 で表現し、最初の訪問時に距離を確定します。

注意ちゅうい:

• 返却値の Vec<i32> は 0-index 頂点順です。

計算量けいさんりょう:

• O(n^2)（密行列の隣接走査）