[ABC288 C] Don't be cycle

https://atcoder.jp/contests/abc288/tasks/abc288_c

閉路を判別する問題。

例1で問題を理解する

このグラフから、

閉路をなくすには何ヶ所の辺を外せばよいか？

ひと目、二カ所の三角を壊せばよさそうなので答えは 2 になる。

解き方

壊すことはできないため最初から作る。その過程ですでに連結していたら辺は作らない。たとえば 1-2-3 が繋がっていれば 1-3 は不要である。

この方法を一歩進めるとクラスカル法になる。

コード (AC)

N, M = gets.split.collect(&:to_i)                    # => [6, 7]
XY = M.times.collect { gets.split.collect(&:to_i) }  # => [[1, 2], [1, 3], [2, 3], [4, 2], [6, 5], [4, 6], [4, 5]]
ds = DisjointSet.new
count = 0
XY.each do |edge|
  if ds.same?(*edge)
    count += 1
  end
  ds.unite(*edge)
end
p count                                              # => 2