Skip to content

Instantly share code, notes, and snippets.

@obelisk68
Last active April 18, 2023 06:35
Show Gist options
  • Save obelisk68/4ae3ba23a5b60be8e5b9d4a42b575c97 to your computer and use it in GitHub Desktop.
Save obelisk68/4ae3ba23a5b60be8e5b9d4a42b575c97 to your computer and use it in GitHub Desktop.
Union Find
#簡素版
class UnionFind
def initialize(size)
@rank = Array.new(size, 0)
@parent = Array.new(size, &:itself)
end
def unite(x, y)
x = root(x)
y = root(y)
return if x == y
if @rank[x] > @rank[y]
@parent[y] = x
else
@parent[x] = y
@rank[y] += 1 if @rank[x] == @rank[y]
end
end
def root(x)
loop do
if @parent[x] == x
return x
else
x = @parent[x]
end
end
end
def same_set?(x, y)
root(x) == root(y)
end
def size
@parent.map { root(_1) }.uniq.size
end
end
#参考
#https://qiita.com/k_karen/items/5349a25c3eb7b4697f58
class UnionFind
def initialize(data)
case data
when Array
size = data.size
@map0 = data.map.with_index.to_h
when Integer
size = data
@map0 = size.times.map { [_1, _1] }.to_h
else
raise "Error"
end
@rank = Array.new(size, 0)
@parent = Array.new(size, &:itself)
end
def unite(x0, y0)
x = root(x0)
y = root(y0)
return if x == y
if @rank[x] > @rank[y]
@parent[y] = x
else
@parent[x] = y
@rank[y] += 1 if @rank[x] == @rank[y]
end
end
def root(x0)
x = @map0[x0]
loop do
if @parent[x] == x
return x
else
x = @parent[x]
end
end
end
def same_set?(x0, y0)
root(x0) == root(y0)
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment