アルゴリズム基礎：素集合データ構造、BFS、および最小全域木
素集合データ構造 (Union-Find)
素集合データ構造（Disjoint Set Union, DSU）は、要素がどのグループに属するかを管理し、グループの統合と判定を効率的に行うための木構造ベースのデータ構造です。
主要な操作
find: ある要素がどのグループ（代表元）に属するかを特定する。
unite: 二つのグループを一つに統合する。
経路圧縮の実装
検索時に再帰的に親を辿り、直 ...
7月24日 07:28 投稿
Kruskal再構築木の学習メモ
前提知識
Kruskal最小/最大全域木アルゴリズム、ダブリング（Binary Lifting）の知識を前提とします。
Kruskal再構築木を構築すると、最小全域木上の2点間のパスの最大重み、および重み ≤ w の辺のみを通って到達可能な点の集合を O(log N) で求めることができます。
近年の競技プログラミングでは出題頻度は控えめですが、該当する問題に遭遇した際に非常に強力なツ ...
5月19日 05:15 投稿