AtCoder Beginner Contest D - Friends Difficulty: 676
This theme, Union Find
This is an application of the typical problem * 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]
Assign the initial value -1 to the array @ parents.
Next, add the initial value -1 of the paired array.
By repeating this, you can get the number of elements in the set of pairs.
sub.rb
@parents = [-3, 0, -2, 2, 0]
In the case of input example 1, if you look at the negative numbers, you can see that they are divided into groups of 3 and 2.
Therefore, the output will be 3, which has the larger group element.
| Ruby | |
|---|---|
| Code length(Byte) | 548 |
| Execution time(ms) | 260 |
| memory(KB) | 15824 |
Referenced site
Recommended Posts