配列の全ての要素(N個)の最小公倍数(LCM)を求めるアルゴリズム
配列 a の全ての要素の最小公倍数(LCM: least common multiple) を求めるアルゴリズムについてです。2つの最小公倍数だけではなく、N個の要素の最小公倍数を求めます。
Input: a = {1, ...
グラフの2頂点が同じ連結成分に属するか判定するアルゴリズム
連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。
グラフ \(G=(V,E)\) 上の2頂点 \(u,v\) が同じ連結成分に属しているか判定するアルゴリズムについてです。 ...
グラフの連結成分の個数を求めるアルゴリズム
連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。
連結成分は3つアルゴリズムグラフ \(G=(V,E)\) の連結成分の個数を数えるアルゴリズム：
「未探索」 ...区間の和を求めるアルゴリズム（区間の更新なし）
要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間 = S + a; }}// - S;}int main() { vector<int>a = {1, 2 ...
二次元での区間和を求めるアルゴリズム（区間の更新なし）
大きさが \(H × W\) の二次元配列 \(a\) 上において、 + a + … + a
+ a + a + … + a
+ …
+ a + a + … + ...
フローネットワークの最小カットの容量を求めるアルゴリズム
最小カットの容量を求めるアルゴリズム：
フローネットワーク \(G=(V,E)\) の最大フロー \(f^*\) の値 \(|f^*|\) を求める\(|f^*|\) が最小カットの容量
...
二部グラフの最大マッチングを求めるアルゴリズム
二部グラフの最大マッチングを求めるアルゴリズム：
二部グラフ \(G=(L \cup R, E)\) に対応する以下のようなフローネットワーク \(G’\) を作る\(G\) にソース \(s\) ...Ford-Fullkerson法による最大フローの値を求めるアルゴリズム
最大フローを求めるアルゴリズム（Ford-Fullkerson法）：
フロー \(f\) を 0 としてはじめるソース(入口) からシンク(出口)までの増加可能経路 \(p\) が残余ネットワーク \ ...
フローネットワークの基礎と用語の定義
関数 \(f : V×V \rightarrow \mathbb{R}\)で表現されるフローは、以下の特徴を持つ重み付き有向グラフ（フローネットワーク） \(G=(V,E)\) 上で定義されます。
ダブリングによる木の最近共通祖先（LCA：Lowest Common Ancestor）を求めるアルゴリズム
最近木においてある頂点の祖先は「親をたどってたどり着ける頂点」を指し、2頂点の共通祖先は「2頂点が共通して持つ祖先」のことを言います。
頂点 u と v の最近共通祖先(LCA: Lowest Common Ancesto ...