emtubasa https://blog.hatena.ne.jp/emtubasa/ ツバサの備忘録 https://emtubasa.hateblo.jp/ Union-Find木 問題 提出コード 解法 全ての橋が崩れた状態では、どの島からも別の島へ行くことができません。 よって、不便さは、すなわち となります。 ということで、ここから逆に橋を組み立てていき、不便さを後ろから求めていくことにします。 今現在の不便さがで、次にを繋ぐ橋をかけるとします。 既にからへ行くことができる場合、不便さが減ることはないので、からへ行くことができない場合を考えていきます。 自身を含む、から行くことができる島の個数を、同様にから行くことができる島の個数をとします。 このとき、に橋をかけることで、に含まれる任意の島から、に含まれる任意の島へ、新しくいくことができるようになるため、 不便さは… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Femtubasa.hateblo.jp%2Fentry%2F2019%2F03%2F03%2F224018" title="ABC120 D - Decayed Bridges - ツバサの備忘録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://cdn.blog.st-hatena.com/images/theme/og-image-1500.png Hatena Blog https://hatena.blog 2019-03-03 22:40:18 rich https://emtubasa.hateblo.jp/entry/2019/03/03/224018 1.0 100%