htkb-proconの日記

初心者がPythonで問題解いた記録

Typical Contest 001-B, ARC032-B, ARC037-B UnionFind

B: Union Find - AtCoder Typical Contest 001 | AtCoder

Submission #1294904 - AtCoder Typical Contest 001 | AtCoder
UnionFindの実装が面倒そうで避けてたので練習として。データ構造としては配列一本持つだけでどのように操作するか/比較するかだったので想像より簡単だった。一応クラス立ててやったけど必要なかった。__get_root()else節で親に直接つなぎ直す経路圧縮だけしている。経路圧縮だけで計算量はO(log n)くらいらしい。

B: 道路工事 - AtCoder Regular Contest 032 | AtCoder

Submission #1294948 - AtCoder Regular Contest 032 | AtCoder
UnionFindで根の数を数えるだけ……なんだけどset(v)の長さをそのまま出力してWAした。根に直接繋がれていないやつももちろんいるので、set(v)で重複を消したあとにそれぞれに対して根の確認を行わなければならなかった。

B: バウムテスト - AtCoder Regular Contest 037 | AtCoder

Submission #1295052 - AtCoder Regular Contest 037 | AtCoder
DFSで解く問題のようだけど。UnionFindで閉路を検出するにはあらかじめ頂点と同じ数のis_tree配列を作って全部1を入れておき、

  1. 同じ根の頂点同士を結合しようとした根
  2. 閉路のあるUnionと結合した根

is_treeにその都度0を入れていき、最後に根に対応するis_treeの合計を数えた。最初2に気付かずWAした。


参考にしたページ: pakapa104.hatenablog.com