🌳

[ABC292 D] Unicyclic Components

2024/02/02に公開

Ruby

辺の数を求める問題。

グラフ問題

この問題の問いである、

すべての連結成分は「節の数 = 辺の数」を満たすか？

はグラフについて言っている。

連結成分が「節の数 - 1 = 辺の数」の素集合森ついて言っていると受け取ってしまうとおかしなことになる。素集合データ構造を使って解けることを知っているからといって問題がそれに寄っているとは限らない。先入観を捨てて落ち着いて読むべし。

例 1 で問題を把握する

(2 3) (1 1) (2 3) の順で辺を作る。このとき2回目に出てきた (2 3) を無視してはいけない。2回目も辺を作るので 2 と 3 の間で二本の辺ができる。また (1 1) も無視してはいけない。1 から 1 への辺ができる。

問題文にはこれらのやや奇妙なルールの説明がないのだが、例1の挙動でそれとなく伝えられている。

まとめると次のようになり、

連結成分	節の数	辺の数	一致？
1	1	1	○
2-3	2	2	○

節と辺の数はがすべて一致するので答えは Yes になる。

独自の入力例

N = 6 で (1 1) (1 1) (2 3) (2 3) (4 5) の辺を作る。

これを目視でまとめると次のようになり、

連結成分	節の数	辺の数	一致？
1	1	2
2-3	2	2	○
4-5	2	1
6	1	0

一部しか一致しないので答えは No になる。

解法

まず、辺に対応する根を集計して「根ごとの辺の数」を求める。

辺	根
1 - 1	1
1 - 1	1
2 - 3	3
2 - 3	3
4 - 5	5

↓ 集計

根	辺の数
1	2
3	2
5	1

次に、素集合森から「根ごとの節の数」を求める。

根	節の数
1	1
3	2
5	2
6	1

最後に、両者を比べる。

根	節の数	辺の数	一致？
1	1	2
3	2	2	○
5	2	1
6	1	0

この表は目視で作った表と同じになっているのがわかる。

コード (AC)

N, M = gets.split.collect(&:to_i)                                    # => [6, 5]
XY = M.times.collect { gets.split.collect(&:to_i) }                  # => [[1, 1], [1, 1], [2, 3], [2, 3], [4, 5]]
ds = DisjointSet.new(1..N).unites(XY)                                # => 親:{1=>1, 2=>3, 3=>3, 4=>5, 5=>5, 6=>6} 構図:{1=>[1], 3=>[2, 3], 5=>[4, 5], 6=>[6]} 節数:{3=>2, 5=>2} 木数:4 高さ:{3=>2, 5=>2}
roots = XY.collect { |x, _| ds.root(x) }                             # => [1, 1, 3, 3, 5]
edge_counts = roots.tally(Hash.new(0))                               # => {1=>2, 3=>2, 5=>1}
node_counts = ds.groups.transform_values(&:size)                     # => {1=>1, 3=>2, 5=>2, 6=>1}
ans = node_counts.all? { |root, count| count == edge_counts[root] }  # => false
puts ans ? "Yes" : "No"

もし、DisjointSet クラス側で辺の数を管理している場合は、

N, M = gets.split.collect(&:to_i)                                   # => [6, 5]
XY = M.times.collect { gets.split.collect(&:to_i) }                 # => [[1, 1], [1, 1], [2, 3], [2, 3], [4, 5]]
ds = DisjointSet.new(1..N).unites(XY)                               # => 親:{1=>1, 2=>3, 3=>3, 4=>5, 5=>5, 6=>6} 構図:{1=>[1], 3=>[2, 3], 5=>[4, 5], 6=>[6]} 節数:{3=>2, 5=>2} 木数:4 高さ:{3=>2, 5=>2}
ans = ds.groups.all? { |root, nodes| nodes.size == ds.edge(root) }  # => false
puts ans ? "Yes" : "No"

としてもよい。