[ARC037 B] バウムテスト
閉路の有無を判定する問題。
辺の喪失
例1は次のグラフになっている。
ところが同様にして素集合森を作ると辺の情報が失なわれる。
(6 7 8) は閉路だったはずだが、その形跡はない。どうやらグループ化は得意だが節と節の正確な繋がりを保持しない素集合森は、閉路の確認に向いていないようだ。
解法1. 偽物の木を除去する
偽物の木
閉路の確認に向いていないとはいえ、これは少しの工夫で対応できる。
- 森を作る過程で辺の両端の節がすでに繋がっているか？
を判定するだけでよい。繋がっていたら閉路のある偽物の木である。正確には「今はまだ閉路のある木かわからないが、続行して連結すると確実に閉路ができてしまう木」である。
問題の問いは「本物の木の数」なので、以上を踏まえると、
- 森を作る過程で辺がすでに繋がっているか？ を調べる
- 繋がっていれば偽物の木なので記録しておく
- 森を作ったあと、木全体から偽物の木たちを除いた残りの木の数が答え
となる。
解法1の実装 (WA)
N, M = gets.split.collect(&:to_i) # => [8, 7]
XY = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2], [2, 3], [2, 4], [5, 6], [6, 7], [6, 8], [7, 8]]
ds = DisjointSet.new(1..N)
closed = Set[]
XY.each do |x, y|
if ds.same?(x, y) # 辺の両端の節がすでに繋がっていたら
closed << ds.root(x) # 閉路のある木として記録する
end
ds.unite(x, y) # 閉路があっても森を作り続ける
end
p ds.tree_count - closed.count # => 1
としてWA。
考え方は間違っていないはずだし、入力例1〜3も通るのに、提出すると一部で WA になるのはどういうことか？
WA の原因
入力を、
N = 5
XY = [[3, 4], [2, 5], [1, 5], [1, 2], [1, 3], [4, 5]]
にして同様に実行すると、
ds = DisjointSet.new(1..N)
closed = Set[]
XY.each do |x, y|
if ds.same?(x, y)
closed << ds.root(x)
end
ds.unite(x, y)
end
森には、
ds.groups # => {4=>[1, 2, 3, 4, 5]}
根4の木が1つしかないのに偽物の木は、
closed # => #<Set: {5, 4}>
2つあると記録している。
にもかかわらず、
- 木の総数(1) - 偽物の木の数(2)
p ds.tree_count - closed.count # => -1
としてしまうから、結果が負になってしまう。木の数が負になるのはおかしい。そもそも根5を持つ木はどこに消えたのか？
木の根は併合によって変化する
それを蔑ろにしていた。closed に入っている 5 と 4 は「森を作る過程で閉路を持っていた木」であって最後まで残っているとは限らない。
正確には、
- 5 → 過去に閉路のあった木 (その後、4と併合する)
- 4 → 現在閉路のある木
となっている。
つまり森
ds.groups.keys # => [4]
から現在閉路のある、もしくは過去に閉路のあった木たち
closed.to_a # => [5, 4]
を除外して、
ds.groups.keys - closed.to_a # => []
その残りを「本物の木たち」としないといけなかった。
解法1の実装の修正 (AC)
N, M = gets.split.collect(&:to_i) # => [5, 6]
XY = M.times.collect { gets.split.collect(&:to_i) } # => [[3, 4], [2, 5], [1, 5], [1, 2], [1, 3], [4, 5]]
ds = DisjointSet.new(1..N)
closed = Set[]
XY.each do |x, y|
if ds.same?(x, y) # 辺の両端の節がすでに繋がっていたら
closed << ds.root(x) # 閉路のある木として記録する
end
ds.unite(x, y) # 閉路があっても森を作り続ける
end
p (ds.groups.keys - closed.to_a).count # => 0
WA でハマったものの森から偽物の木を除外するこの方法は理解しやすい。
解法2. 本物の木をカウントする
本物の木
本物の木は余分な辺がない。
最小限の辺で構成されていて、
- (節の数 - 1) = 辺の数
が成り立つ。
実際に当てはめてみると、
- 1 2 3 4 の木 → (4 - 1) = 3 → ○
- 5 6 7 8 の木 → (4 - 1) = 4 → ×
となるので、その条件で本物の木だけをカウントする。
本当の辺
冒頭でも書いたが、素集合森は辺の情報が欠けている。二つの節を渡して併合するのだから、覚えておいてくれていてももよさそうに思えるが、形状無視でまとめることに特化している素集合データ構造は、そういうところは苦手である。
だったら欠ける前の情報を使えばいい。
入力時の辺を本当の辺として扱い、その辺が属する木の根を列挙し、
XY # => [[1, 2], [2, 3], [2, 4], [5, 6], [6, 7], [6, 8], [7, 8]]
roots = XY.collect { |x, _| ds.root(x) } # => [2, 2, 2, 6, 6, 6, 6]
集計すると、
edge_counts = roots.tally(Hash.new(0)) # => {2=>3, 6=>4}
2の木は3つの辺を持ち、6の木は4つの辺を持つのがわかる。
しかし、実際の森は、
ds.groups # => {2=>[1, 2, 3, 4], 6=>[5, 6, 7, 8]}
となっている。
根2の木が本物の木だとすると辺の数は 3 であり、edge_counts の 2 => 3 と一致するので、根2の木は本物の木だと判断できる。一方、根6の木は辺の数が想定より多いので偽物の木である。
本物の木だけをカウントするのは、
ds.groups.count { |root, nodes| nodes.size.pred == edge_counts[root] } # => 1
でよい。
解法2の実装 (AC)
N, M = gets.split.collect(&:to_i) # => [8, 7]
XY = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2], [2, 3], [2, 4], [5, 6], [6, 7], [6, 8], [7, 8]]
ds = DisjointSet.new(1..N).unites(XY)
edge_counts = XY.collect { |x, _| ds.root(x) }.tally(Hash.new(0)) # => {2=>3, 6=>4}
p ds.groups.count { |root, nodes| nodes.size.pred == edge_counts[root] } # => 1
考え方が少し難しいけど解法は美しい。
解法2の別実装 (AC)
素集合森の方で辺の大きさがわかるように実装している場合はもっと簡潔に書ける。
N, M = gets.split.collect(&:to_i) # => [8, 7]
XY = M.times.collect { gets.split.collect(&:to_i) } # => [[1, 2], [2, 3], [2, 4], [5, 6], [6, 7], [6, 8], [7, 8]]
ds = DisjointSet.new(1..N).unites(XY)
p ds.groups.count { |root, nodes| nodes.size.pred == ds.edge(root) } # => 1
閉路のある木は存在する
閉路のある木は存在しない前提で進めていたが本当は存在する。
- https://www.higashiyama.city.nagoya.jp/blog/2020/04/post-4025.html
- https://karapaia.com/archives/52008050.html
- https://naturelog.main.jp/plants194.html
Discussion