Strongly Connected Components（強連結成分分解）計算量 https://atcoder.github.io/ac-library/production/document_ja/scc.html run(void) 有向グラフを強連結成分分解する 戻り値 g: 強連結成分分解した隣接リスト groups: 閉路毎の頂点集合（トポロジカ…

BFS（幅優先探索）計算量 BFS開始頂点は複数になることも多いので配列を渡す 昇順に頂点を遷移したいときは queue を priority_queue にする std::queue<long long> q; → std::priority_queue<long long, std::vector<long long>, std::greater<long long>> pq; #include <bits/stdc++.h> namespace NyaaLIB { struct BFS_ARG { using</bits/stdc++.h></long></long></long>…

【木のDAG】 木に単一の方向性を持たせるとDAGになる 割り振り直した頂点IDは降順あるいは昇順になる このようなDAGは木でもあるので元の頂点IDはユニークでもある 頂点の割り振り直し方法 ・DAGの最長経路＝木の根からの深さ＝末端からMAXのBFS、で頂点IDを…

フィボナッチ数列の計算（メモ化再帰のテンプレートとしても使える） #include <bits/stdc++.h> using namespace std; using ll = long long; using vl = vector<ll>; auto mf = [&](auto self, ll now, vl& memo, ll inf) -> void { if (now == 1 || now == 2) { // 末端は定数</ll></bits/stdc++.h>…

ウェーブレット行列 任意区間のK番目の要素を高速に取得するデータ構造 https://ei1333.github.io/library/structure/wavelet/wavelet-matrix.cpp.html前計算 クエリ WaveletMatrix(v): 各要素の高さ v を初期値として構築する. access(k): k 番目の要素を返…

写像12相ライブラリ ただし写像12相以外の組み合わせ計算も含む Pow(x, n): 繰り返し二乗法 P(n, r): 順列 C(n, r): 組み合わせ H(n, r): 重複組み合わせ IEP(n, r): 包除原理 Stirling(n, r): 第二種スターリング数 Catalan(n): カタラン数 #include <bits/stdc++.h> names</bits/stdc++.h>…

クラスカル法 重み付き連結グラフの最小全域木を求める 引数 ARG_Kruskal n: 頂点数 g: 重み付き隣接リスト 戻り値 最小全域木となる辺 {from, to, cost} の集合を返す 依存クラス DS_UnionFind https://9871225.hatenablog.com/entry/2022/03/02/202403 #in…

Union Find DS_UnionFind(n): 半開区間[0,n) のデータ構造を確保 以下で処理できる関数 Union(x, y): xとyを結合 Find(x): xの根を返す Max(x): xが属する集合の最大値を取得 Min(x): xが属する集合の最小値を取得 Same(x, y): xとyが同じ集合どうか判定 Siz…

template<class T1, class T2>static mint Pow(T1 x, T2 n) 繰り返し二乗法で を計算する 計算量 namespace LIB { template<long long mod>class ModINT { using mint=ModINT; using ll=long long; ll inv(ll a, ll m) { ll b=m,u=1,v=0; while(b) { ll t=a/b; a-=t*b,swap(a,b); u-=t*v,swap(u,</long></class>…