Submission #420239

---

Source Code Expand

class Node
    attr_accessor :parent, :rank
    def initialize(n)
        @parent = n
        @rank = 0
    end
end

class UnionFindTree
    attr_accessor :nodes, :count
    def initialize(n)
        @nodes = (0..n).to_a.map { |i| Node.new(i) }
        @count = n
    end
    def find(x)
        return x if @nodes[x].parent == x
        return @nodes[x].parent = find(@nodes[x].parent)
    end
    def unite(a, b)
        a = find(a)
        b = find(b)
        return if a == b
        if @nodes[a].rank < @nodes[b].rank
            @nodes[a].parent = b
        else
            @nodes[b].parent = a
            @nodes[b].rank += 1 if @nodes[a].rank == @nodes[b].rank
        end
        @count -= 1
    end
    def same?(a, b)
        find(a) == find(b)
    end
    def parents
        @nodes.map(&:parent)
    end
    def rank
        @nodes.map(&:rank)
    end
end

n, q = gets.split.map(&:to_i)
uf = UnionFindTree.new(n)
q.times do
    p, a, b = gets.split.map(&:to_i)
    case p
    when 0
        uf.unite(a,b)
    when 1
        puts uf.same?(a,b) ? "Yes" : "No"
    end
end

Submission Info

Judge Result