クラスカル法など、他ライブラリから呼ばれることがあるので実装を置いておく。 前提 グループの管理を高速で行うことができるデータ構造 実態は木（森）になっている ある状態から、グループを併合することができ、分割することはできない UnionFind木の機…

前提 いずれも発想は貪欲法である。 クラスカル法 実装内容の理解についてはクラスカル法の方が楽 頂点数に対応する大きさのUnionFind木を用意する グラフの辺を、重みの小さい順に見ていき、(u, v)がまだ同じグループに属していないならばその辺を採用する…

前提 ダブリング手順 dp[i][j]:=頂点iの2j個上の頂点 iは頂点数nに対して、log_n 初期化: まずdpを-1で初期化したのち、dp[0][j]、つまり1個上のノードを登録する 以降、dp[i+1][j]=dp[i][dp[i][j]] で更新 ダブリングのわかりやすい解説 satanic0258.hatena…

セグメント木を抽象化したライブラリ(C++)を作成したのでまとめておく。 前提 セグメント木の実態は完全二分木 要素数nを扱いたいならn以上の2冪を葉の数とし、その数をwとすると、全体の要素数は2*w-1個となる 完全二分木において、要素i(>0)の親は(i-1)/2…