ARC 097 D Equals

競技プログラミング

ポスター発表が終わりました。えぬわいです。

qiita.com

続きです。

atcoder.jp

概要

1 から N までの数列をシャッフルする。ある数字の組みが与えられるので、その組みの位置をスワップして、最大何個まで元の位置に戻せるかという問題。

考えたこと

組みとして、(1, 2)と(2, 3)のような組みが与えられたとき、共通する数字があれば、与えられた数字の集合は、すべて入れ替えられる。これを、Union-Findで記録していく。p の i 番目の中身が、5 だったとき、それを p の 5 番目に移動させるには、5 が入っている位置と、p の 5 番目が同じ、グループに入っていれば良いので、蟻本の関数を使うと、same(p[i], i) が Trueなら、p[i] = i という関係にすることができる。

以下、解答。

N, M = map(int, input().split())

p = list(map(int, input().split()))

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for i in range(n)]

    def find(self, x):
        if self.par[x] == x:
            return x
        self.par[x] = self.find(self.par[x])
        return self.par[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        elif self.rank[y] < self.rank[x]:
            self.par[y] = x
        else:
            self.rank[y] += 1
            self.par[x] = y
        

uf = UnionFind(N)

for i in range(M):
    x, y = map(int, input().split())
    uf.unite(x-1, y-1)

ans = 0
for i in range(N):
    if uf.find(p[i]-1) == uf.find(i):
        ans += 1

print(ans)

通った！！！！