Submission #2529643

---

Source Code Expand

class UnionFind
    def initialize(n)
        @par = Array.new(n)
        n.times{ |i| @par[i] = i }
        @rank = Array.new(n, 0)
    end

    def find(x)
        if @par[x] == x
            x
        else
            @par[x] = find(@par[x])
        end
    end

    def unite(x,y)
        x = find(x)
        y = find(y)
        return if x == y

        if @rank[x] < @rank[y]
            @par[x] = y
        else
            @par[y] = x
            @rank[x] += 1 if @rank[x] == @rank[y]
        end
    end

    def same?(x, y)
        find(x) == find(y)
    end
end

# edge = [src, dst, cost]
def kruskal(n, edges)
    edges = edges.sort_by{|edge| edge[2]}
    uf = UnionFind.new(n)
    res = 0
    edges.each do |edge|
        u = edge[0]
        v = edge[1]
        unless uf.same?(u, v)
            uf.unite(u, v)
            res += edge[2]
        end
    end
    return res
end


N = gets.to_i
xys = []
N.times do |i|
    xys[i] = [i] + gets.split.map(&:to_i)
end

xsort = xys.sort_by{|arr| arr[1]}
ysort = xys.sort_by{|arr| arr[2]}

edges = []
(N-1).times do |i|
    m, n = xsort[i][0], xsort[i+1][0]
    dist = [(xys[m][1]-xys[n][1]).abs, (xys[m][2]-xys[n][2]).abs].min
    edges.push([m, n, dist])
    m, n = ysort[i][0], ysort[i+1][0]
    dist = [(xys[m][1]-xys[n][1]).abs, (xys[m][2]-xys[n][2]).abs].min
    edges.push([m, n, dist])
end

puts kruskal(N, edges)

Submission Info

Judge Result