Union Find
問題 問題概要 盤面上での陸地の繋がりを調べえる問題。ただし、1マス分だけ陸地にすることができる。 解法 10x10の盤面で小さいので、100個あるマスを1つ変えた時に、どうなるかを調べる。全探索するということ。 回りの4方向で陸どおしでつながっている部…
問題 問題概要 省略 解法 union findは辺を削除することができない。問題は、クエリを与えられた順にみると、辺を削除するような形だが、クエリを逆からみれば、辺をつなげていく形になる。このようになると、union findで管理できる。 また今回学んだunion …
問題 問題概要 s->iへ到達できるか。ただし、通れる頂点に制約あり。 解法 思いついたのは、逆からunion-find。頂点iに行けるかを見る場合、i以上の頂点を使い、sからiへたどり着けるかを見れば良いので、i=n-1からi=0の順に調べ、そのつど、追加できる辺を…
問題 問題概要 頂点1からnまで達するために、必要な辺の長さの最小値。ただし、最小値は10の倍数 解法 大まかな方針として、必要な辺の長さを求めるので、Xcm以下の辺の長さだけでunion-findを使いグラフを形成して、1からnに達するか(同じ連結成分に含まれ…
unionfind tree構造を用いる問題