rustのpetgraph crateを使ってみる

TL;DR

rustのpetgraphクレートを使うとグラフ構造が色々扱えるらしいので、触ってみた。
順次追記していく予定。

union find tree

グループ分けを管理するデータ構造。

1. 要素xとyが同じグループに属するかの判定
2. 要素xとyの属するグループを併合

みたいなことができるらしい。自分で実装してみても良かったが、petgraphクレートでは経路圧縮とランクを考慮した実装がされていて、1, 2を$O(α(n))$で処理できるらしいので、そのまま使えばいいかってなった。

use petgraph::unionfind::UnionFind;

// Union Find Treeの初期化
let mut tree :UnionFind<usize> = UnionFind::new(N);

// x, yのグループを結合
tree.union(x, y);

// x, yが同じグループに属しているか判定
let flag: bool = tree.equiv(x, y);