Résolution avec Ruby AtCoder ABC177 D Union Find

introduction

• Problèmes AtCoder * Utilise les recommandations pour résoudre les problèmes passés. Merci à AtCoder et AtCoder Problems.

Ce thème

AtCoder Beginner Contest D - Friends Difficulty: 676

Ce thème, Union Find

Ceci est une application du problème typique * 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]

Attribuez la valeur initiale «-1» au tableau «@ parents». Ensuite, ajoutez la valeur initiale «-1» du tableau apparié. En répétant cela, vous pouvez obtenir le nombre d'éléments dans l'ensemble de paires.

sub.rb

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

Dans le cas de l '«exemple d'entrée 1», si vous regardez les nombres négatifs, vous pouvez voir qu'ils sont divisés en groupes de «3» et «2». Par conséquent, la sortie sera "3", qui a l'élément de groupe le plus grand.

Résumé

• Résolu ABC 177 D
• Familiarisez-vous avec Ruby

Site référencé

• Rapport de participation au concours AtCoder pour débutants 177 *