Union-find

atcoder.jp・参考 AtCoder Regular Contest 106 B – Values を解いた記録 – Manuel1024の引きこもルーム・説明 Union-Findを使って実装した。操作によって連結成分毎の合計は変わらないことので、もし変わっていればNoになる。 atcoderで新しく使えるようになったac-library-python/atcoder at master · not522/ac-library-python · GitHubを使って実装した。 from atcoder import dsu n,m=map(int,input().split()) a=…

ABC229E クエリ逆算，クエリの差分辺の削除より，辺の追加の方が簡単なので，そちらで考える． 一つ頂点を追加したときに，connected component がどの程度変化するのか， 差分を求めることで高速にクエリを処理する． 大きい番号から頂点を追加していくので， 辺を追加するときは，小さい番号から大きい番号への辺のみを追加する． 連結成分の個数の変化 頂点を追加したときに \(+1\) 個． 辺 \*1 uf.merge(a,i), c--; } ans.push_back(c); } reverse(all(ans)); srep(i,1,ans.size()) cout << a…

ABC238E 累積和をを求めるのと同値． \(s_{i} := \sum_{j \in i} a_{i}\)とする． 与えられる情報は，\(s_{r} - s_{l}\) となる． ここで \(s_{l}, s_{r}\) の内，一方が分かればもう一方が分かることになる． また，最初に分かっていることは，\(s_{0} = 0\) ということだけである． これらを整理すると，グラフで考えることができる． 頂点は \(0, 1, \cdots N+1\) とする．つまり，累積和 \(s\) の index. 与えられた情報を \(s_{r} - s_{l}\) とする． このとき，頂点\(r,…

ABC264E Union-find, クエリ先読み，クエリの逆算． 切断するのは難しいが，結合するのは Union-find を用いれば簡単． クエリを先読みして，逆算すれば結合に書き換えられる． 実装\(M\) 個の発電所は，役割がすべて同じなので区別する必要がない． よって，一つの頂点だと思っておくと良い． 問題によっては，超頂点を用意して，超頂点から \(M\) 個の発電所に辺を張る という実装も考えられる．答えを配列に入れていくが，クエリの開始時点の状態または終了時点を追加することで， \(Q+1\) の長さにすると楽． 使っている記号，マクロ等 "https://ecsmtlir.…

ABC293D \(N\) 個の頂点を2倍して \(2N\) 個の頂点とみなしたグラフを考える． ひもが結ばれているとき，グラフの方で辺があるとみなす． 各連結成分に対して，サイクルになっているかを判定すれば良い． 実装するときは， 初期で \(a,a'\) が繋がっている事になる． 使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925" int main() { ll n, m ; cin >> n >> m; vvll to(2*n); UnionFind<ll> uf(n); rep(i,m){ ll …

ABC040D グラフとクエリがあるが，いずれも年に関して降順ソートする． ソートすることで，クエリ毎にUnion-find を作り直す必要が無くなり， 同じUnion-find を使いまわせる．年が同じときは，クエリに答える方を，Union-find の merge より先に行う． 使っている記号 int main() { ll n, m, k, q; cin >> n >> m; UnionFind<ll> uf(2e5+10); vector<vector<pll>> road(2e5+10), query(2e5+10); rep(i,m){ ll a,b,y; cin >> a >>…