問題 問題概要 省略。 解法 union find を使って、連結成分がいくつできているかを数得ればよい。連結成分を１つにするのに必要な辺の数は答えになるので、答えは(連結成分の数-1)となる。 ミス なし。 コード #include <bits/stdc++.h> using namespace std; typedef long </bits/stdc++.h>…

問題 問題概要 盤面上での陸地の繋がりを調べえる問題。ただし、1マス分だけ陸地にすることができる。 解法 10x10の盤面で小さいので、100個あるマスを1つ変えた時に、どうなるかを調べる。全探索するということ。 回りの4方向で陸どおしでつながっている部…

問題 問題概要 省略 解法 union findは辺を削除することができない。問題は、クエリを与えられた順にみると、辺を削除するような形だが、クエリを逆からみれば、辺をつなげていく形になる。このようになると、union findで管理できる。 また今回学んだunion …