各種アルゴリズムの C++ による実装 by 前原さん
http://www.prefield.com/algorithm/index.html
基本
テンプレート
グラフ
基本要素
グラフの基本要素
連結成分
関節点，二重頂点連結成分分解
橋，二重辺連結成分分解
強連結成分分解
最短路
単一始点最短路 (Dijkstra)
単一始点最短路 (Bellman-Ford)
k-最短路
全点対間最短路 (Johnson)
全点対間最短路 (Floyd Warshall)
全域木
最小全域木 (Prim)
最小全域森 (Kruskal)
最小直径全域木 (Cuninghame-Green)
最小全域有向木 (Chu-Liu/Edmonds)
最小シュタイナー木 (Dreyfus-Wagner)
フロー・カット
最大流 (Edmonds-Karp)
最大流 (Dinic)
最大流 (Goldberg-Tarjan)
無向グラフの全域最小カット (Nagamochi-Ibaraki/Stoer-Wagner)
Gomory-Hu 木
最小費用流 (Primal Dual)
マッチング
二部グラフの最大マッチング
二部グラフの最小重み最大マッチング
二部グラフの辺彩色
最大マッチング
最小重み最大マッチング
ツリー
木の同型性判定
オフライン最小共通先祖 (Tarjan)
木の高さ
木の直径
周遊路
有向オイラー路
無向オイラー路
有向中国人郵便配達問題
無向中国人郵便配達問題
最短ハミルトン路
その他
トポロジカルソート
グラフの同型性判定
平面幾何
基本要素
平面幾何の基本要素
点の進行方向 (ccw)
直線・線分
交差判定など
距離など
多角形
端点
点-多角形包含判定
多角形の面積
多角形の摂動変形
単純多角形の三角形分割 (耳分解)
凸多角形
凸包 (Andrew's Monotone Chain)
凸性判定
凸多角形の切断
凸多角形の共通部分
凸多角形の直径
凸多角形の端点
点-凸多角形包含判定
幾何グラフ
ドロネー三角形分割
線分アレンジメント
可視グラフ
線分交差問題 (嘘平面走査)
線分併合
点位置決定 (スラブ分解)
領域探索 (kd 木)
最近点対
双対変換
線分串刺し直線
直線アレンジメント走査
未整理
空間幾何
空間幾何の基本要素
最小包含球 (move-to-front heuristics)
データ構造
二分探索木
AVL木
赤黒木
Splay木
Treap
Union Find
区分木
Fenwick木
Range Minimum Query
文字列
基本操作
std::string の基本操作
文字列検索
単一パターン検索 (Shift And)
単一パターン検索 (Knuth-Morris-Pratt)
単一パターン検索 (Boyer-Moore)
複数パターン検索 (Aho-Corasick)
二次元パターン検索 (Baker-Bird)
文字列検索その他
正規表現
ワイルドカードマッチング
文字列系データ構造
Directed Acyclig Word Graph
Trie
Suffix Array (Larsson-Sadakane)
文字列処理その他
最長繰り返し部分文字列(Karp Miller Rosenberg)
二乗判定
最長回文 (Manacher)
再帰下降型構文解析 ( LL(1) )
ソート
クイックソート
k 番目の要素の選択
マージソート
バブルソートの交換回数
計数ソート
数理
整数
整数の基本要素
多倍長整数
素数
エラトステネスのふるい
アトキンのふるい
区間ふるい
確率的素数判定
ガウス素数判定
法演算
ユークリッドの互除法
逆元
線型連立合同式
べき剰余
ヤコビ記号
平方剰余
数論的関数
オイラーのφ関数
メビウスのμ関数
カーマイケルのλ関数
有理数
Stern-Brocot 木
有理数型
行列演算
行列
LU分解
固有値・固有ベクトル
最適化
上凸関数の最大値 (黄金探索法)
単調関数の零点 (二分法)
線型計画法 (二段階単体法)
無制約非線型最適化 (準Newton法)
割り当て問題 (ハンガリアン法)
その他
高速フーリエ変換
典型動的計画法
連鎖行列積問題
最長増加部分列 ( O(n log n) )
最長増加部分列 ( O(n^2) )
最長共通部分列 ( O( (n+r) log n ) )
最長共通部分列 ( O(n^2) )
硬貨両替問題
配列アラインメント (Needleman-Wunsch)
部分集合和問題
ナップサック問題
典型バックトラック
支配集合問題
その他
さいころ
ポーカー役判定
区間が覆う長さ
対和からの復元
ハニカム構造
日付関連
2充足可能性問題
半順序集合の最小鎖分割
安定マッチング
区間スケジューリング
brainfuckインタプリタ
探索
深さ優先探索
幅優先探索
両側探索
A^* 探索
反復深化
