2020年3月20日グラフ幅優先探索,グラフ,深さ優先探索,連結成分,Union-Find,連結成分のサイズ,同じ連結成分か判定

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

グラフ \(G=(V,E)\) 上の2頂点 \(u,v\) が同じ連結成分に属しているか判定するアルゴリズムについてです。 ...

2020年3月20日グラフ幅優先探索,グラフ,深さ優先探索,連結成分,連結成分の数

連結成分とは、「任意の2頂点間にパスが存在するような部分グラフのうち極大なもの」のことを言います。

連結成分は3つアルゴリズム

グラフ \(G=(V,E)\) の連結成分の個数を数えるアルゴリズム:

「未探索」 ...

2020年3月20日その他区間和,区間,累積和,配列

要素数 N の数列 \(\{a_0, a_1, a_2, \cdots, a_{N-1}\}\) が与えられた時に、区間 = S + a; }}// - S;}int main() { vector<int>a = {1, 2 ...

2020年3月20日その他

大きさが \(H × W\) の二次元配列 \(a\) 上において、 + a + … + a
+ a + a + … + a
+ …
+ a + a + … + ...

グラフ競プロ,フロー,最大フロー,Ford-Fulkerson,フローネットワーク,最大フロー・最小カット定理,カット,最小カット

アルゴリズム

最小カットの容量を求めるアルゴリズム:

フローネットワーク \(G=(V,E)\) の最大フロー \(f^*\) の値 \(|f^*|\) を求める
\(|f^*|\) が最小カットの容量

...

2020年3月20日グラフ競プロ,フロー,最大フロー,二部グラフ,最大マッチング,マッチング

アルゴリズム

二部グラフの最大マッチングを求めるアルゴリズム:

二部グラフ \(G=(L \cup R, E)\) に対応する以下のようなフローネットワーク \(G’\) を作る\(G\) にソース \(s\) ...

2020年3月19日グラフ競プロ,フロー,最大フロー,Ford-Fulkerson,フローネットワーク,最大フロー・最小カット定理

アルゴリズム

最大フローを求めるアルゴリズム(Ford-Fullkerson法):

フロー \(f\) を 0 としてはじめる
ソース(入口) からシンク(出口)までの増加可能経路 \(p\) が残余ネットワーク \ ...

グラフフロー,フローネットワーク,用語・定義

フローフローとフローネットワーク

関数 \(f : V×V \rightarrow \mathbb{R}\)で表現されるフローは、以下の特徴を持つ重み付き有向グラフ(フローネットワーク) \(G=(V,E)\) 上で定義されます。

2020年3月16日グラフ,競プロ,LCA,ダブリング,木の2頂点間の距離,木のパス上に頂点があるか

最近木においてある頂点の祖先は「親をたどってたどり着ける頂点」を指し、2頂点の共通祖先は「2頂点が共通して持つ祖先」のことを言います。

頂点 u と v の最近共通祖先(LCA: Lowest Common Ancesto ...

2020年3月15日AtCoder競プロ,セグメント木,区間,更新,データ構造,set,imos法,遅延評価セグメント木,イベントソート,座標圧縮

問題へのリンク

問題概要

 N 回の通行止めがあり、 Q 人の人ははじめ座標 0 に立っている。 
\(i\) 番目の道路工事は時刻&n ...