ABC 049 D 連結が解けたのが嬉しかったので解説してみた(ちなみに43分かかった)。 Union-Find木を使う問題である。 タイトルからして、「ああ、グラフの連結成分求める問題か。Union-Find使えば楽勝じゃん」とか思って取り掛かった。 ・・・・・・甘かった。…

蟻本を読みながらけんちょんさんの記事に載っている問題を毎日解いているが、LISの項でこの問題が分からず、やむを得ず他の人の解答を見たときに学んだことが多かったのでメモ。 ・upper_boundではなくlower_boundを使う ・答えの探し方(lower_bound使う) ・…

蟻本を読んでいたら、クラスカル法の正当性の証明が省略されていたので、自分で証明を構築してみた。 誰かの役に立つといいな。 ちなみにTeXで書く元気はなかった。汚くてごめんなさい。 クラスカル法の正当性の証明 連結な無向グラフG上のクラスカル法を考…

何番煎じか分からないけどやってみた。 （蟻本だとクラスや構造体にまとめてなくてとっ散らかってたため） #include<bits/stdc++.h> using namespace std; struct union_find{ vector<int> par; vector<int> rank; union_find(int n){ rank = vector<int>(n,0); for(int i=0; i</int></int></int></bits/stdc++.h>