アルゴリズム基礎：素集合データ構造、BFS、および最小全域木
素集合データ構造 (Union-Find)
素集合データ構造（Disjoint Set Union, DSU）は、要素がどのグループに属するかを管理し、グループの統合と判定を効率的に行うための木構造ベースのデータ構造です。
主要な操作
find: ある要素がどのグループ（代表元）に属するかを特定する。
unite: 二つのグループを一つに統合する。
経路圧縮の実装
検索時に再帰的に親を辿り、直 ...
7月24日 07:28 投稿
NOIP2013 提高組: 貨物輸送経路の最大最小辺問題
問題概要
無向グラフが与えられ、各辺には重みが付与されています。クエリでは2頂点間の経路における最小辺重みの最大値を求める必要があります。グラフは非連結の可能性があり、効率的な解法が求められます。
解法アプローチ
最適経路は最大ボトルネック生成木(MBST)上に存在します。MBSTはKruskal法を重み降順で適用して構築します。非連結グラフ対応のため、Union-Find ...
7月1日 17:43 投稿
グラフ理論の基本問題とアルゴリズム実装ガイド
1. 隣接リスト構築と辺のソート
グラフデータをメモリ効率的に扱う場合、各頂点から伸びる辺を格納する配列の配列（隣接リスト）が一般的です。読み込み後、必要に応じて各頂点の接続リストを昇順にソートすることで、辞書順など特定の出力要件を満たせます。
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int m ...
6月4日 00:08 投稿