ruby.rb

class UnionFind
  def initialize(n)
    @parents = Array.new(n, -1)
  end
  def find(x)
    @parents[x] < 0 ? x : @parents[x] = find(@parents[x])
  end
  def parents
    @parents
  end
  def union(x, y)
    x = find(x)
    y = find(y)
    return if x == y
    if @parents[x] > @parents[y]
      x, y = y, x
    end
    @parents[x] += @parents[y]
    @parents[y] = x
  end
end

n, m = gets.split.map(&:to_i)
u = UnionFind.new(n)
m.times do
  a, b = gets.split.map(&:to_i)
  u.union(a - 1, b - 1)
end
puts u.parents.select{ _1 < 0 }.size - 1

sub.rb

puts u.parents.select{ _1 < 0 }.size - 1 #cette fois

puts -u.parents.min #Dernière fois

Changez simplement la dernière ligne de Last time --Qiita en ʻAC`.

sub.rb

@parents = [-3, 0, -2, 2, 0]

Expliquer dans l '«exemple d'entrée 1» précédent, dans «u.parents», «u.parents [0]» et «u.parents [2]» peuvent être divisés en deux groupes représentatifs. Ce n'est pas grave si vous le connectez à une seule route.

Version Ruby de la bibliothèque AtCoder (ACL)

Il y a aussi un mouvement pour créer une version Ruby d'ACL à here --github. C'est «attention requise».

Résumé

• Résolu ACLBC C
• Familiarisez-vous avec Ruby

Site référencé

• Résolution avec Ruby AtCoder ABC177 D UnionFind --Qiita *