Submission #2497462

---

Source Code Expand

class UnionFind
    attr_reader :set_size
    def initialize(n)
        @par = Array.new(n)
        n.times{ |i| @par[i] = i }
        @rank = Array.new(n, 0)
        @set_size = 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
            @set_size[y] += @set_size[x]
        else
            @par[y] = x
            @set_size[x] += @set_size[y]
            @rank[x] += 1 if @rank[x] == @rank[y]
        end
    end

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

N, M = gets.split.map(&:to_i)
ps = gets.split.map(&:to_i)

uf = UnionFind.new(N)
M.times do |i|
    x, y = gets.split.map(&:to_i)
    uf.unite(x-1, y-1)
end

ans = 0
N.times do |i|
    ans += 1 if uf.same?(i, ps[i] - 1)
end

puts ans

Submission Info

Judge Result