Lösen mit Ruby AtCoder ABC177 D Union Find

Einführung

• AtCoder-Probleme * Verwenden Sie Empfehlungen, um frühere Probleme zu lösen. Dank AtCoder und AtCoder Probleme.

Dieses Thema

AtCoder Beginner Contest D - Friends Difficulty: 676

Dieses Thema, Union Find

Dies ist eine Anwendung des typischen Problems * B - Union Find - AtCoder *. Ruby

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.min

sub.rb

    @parents = Array.new(n, -1)

    @parents[x] += @parents[y]

Weisen Sie dem Array "@ parent" den Anfangswert "-1" zu. Fügen Sie als Nächstes den Anfangswert "-1" des gepaarten Arrays hinzu. Wenn Sie dies wiederholen, können Sie die Anzahl der Elemente in der Menge der Paare ermitteln.

sub.rb

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

Wenn Sie im Fall von "Eingabebeispiel 1" die negativen Zahlen betrachten, sehen Sie, dass sie in Gruppen von "3" und "2" unterteilt sind. Daher ist die Ausgabe "3", die das größere Gruppenelement enthält.

Zusammenfassung

• Gelöstes ABC 177 D.
• Machen Sie sich mit Ruby vertraut

Referenzierte Site

• Teilnahmebericht des AtCoder-Anfängerwettbewerbs 177 *