🌳

[ARC032 B] 道路工事

2024/01/23に公開

Ruby

木の数を求める問題。

言葉を置き換える

交差点と言われると車や人が行き交う喧騒を想像してしまう。人間が短期記憶に置いておけるのは7つとか4つとか言われているのだけど、交差点と言われただけで自分だったら少なくとも3つぶんは消費してしまう。そこで脳に優しい言葉に置き換える。

交差点 → 節
道路 → 辺

問題を言い換える

問題が単純化されると「木と木を繋げるには何本の紐が必要か？」と読める。

紐の数を求めるには？

森を作る
木の数を求める
紐の数 = 木の数 - 1

で求まる。

紐の数は、

木が2つ → 繋ぐ紐は1つ
木が3つ → 繋ぐ紐は2つ

だから「木の数 - 1」が答えになる。

特殊な状況を考慮する

ただし、すべての交差点と行き来できる場合は 0 を出力せよ

「すべての交差点と行き来できる」とは木が1本ということ。つまり繋ぐ相手がいないので、何もしなくても 1 - 1 で 0 になる。ただ交差点が一つもない場合はどう解釈すればよいのか？このように特殊なケースを考慮しないと、テストは通るのに提出すると WA になったりする。

ただ今回は「N は 1 以上」と書いてある。つまり木は 0 本にならないので特別な処理は必要ないのがわかる。

例1のシミュレーション

1 から 4 の木があって 1 と 2 を繋ぐ。

1 と 3 を繋ぐ。

その結果、1-2-3 と 4 の 2 つの木ができて、これを繋げるには 1 本の紐があればよい。したがって答えは 1 になる。

コード (AC)

N, M = gets.split.collect(&:to_i)                    # => [4, 2]
AB = M.times.collect { gets.split.collect(&:to_i) }  # => [[1, 2], [1, 3]]
p DisjointSet.new(1..N).unites(AB).tree_count.pred   # => 1