Problem:


Score : 400 points

Problem Statement

We have a permutation of the integers from 1 through N, p_1, p_2, .., p_N.
We also have M pairs of two integers between 1 and N (inclusive), represented as (x_1,y_1), (x_2,y_2), .., (x_M,y_M).
AtCoDeer the deer is going to perform the following operation on p as many times as desired so that the number of i (1 ≤ i ≤ N) such that p_i = i is maximized:

Choose j such that 1 ≤ j ≤ M, and swap p_{x_j} and p_{y_j}.

Find the maximum possible number of i such that p_i = i after operations.

Constraints

2 ≤ N ≤ 10^5

1 ≤ M ≤ 10^5

p is a permutation of integers from 1 through N.

1 ≤ x_j,y_j ≤ N

x_j ≠ y_j

If i ≠ j, \{x_i,y_i\} ≠ \{x_j,y_j\}.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
p_1 p_2 .. p_N
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the maximum possible number of i such that p_i = i after operations.

Sample Input 1

5 2
5 3 1 4 2
1 3
5 4

Sample Output 1

2

If we perform the operation by choosing j=1, p becomes 1 3 5 4 2, which is optimal, so the answer is 2.

Sample Input 2

3 2
3 2 1
1 2
2 3

Sample Output 2

3

If we perform the operation by, for example, choosing j=1, j=2, j=1 in this order, p becomes 1 2 3, which is obviously optimal.
Note that we may choose the same j any number of times.

Sample Input 3

10 8
5 3 6 8 7 10 9 1 2 4
3 1
4 1
5 9
2 5
6 5
3 5
8 9
7 9

Sample Output 3

8

Sample Input 4

5 1
1 2 3 4 5
1 5

Sample Output 4

5

We do not have to perform the operation. 



Sample input:
5 2
5 3 1 4 2
1 3
5 4


Sample output:
2

Submission status: Accepted

Solution code:
from collections import deque
n,m = map(int,input().split())
p = list(map(int,input().split()))
route = [[] for i in range(n+1)]
for i in range(m):
    a,b = map(int,input().split())
    route[a].append(b)
    route[b].append(a)
visit = [False for i in range(n+1)]
atumari = []
for i in range(1,n+1):
    if visit[i]:
        continue
    visit[i] = True
    kar = set([i])
    d = deque()
    d.append(i)
    while d:
        now = d.popleft()
        for j in route[now]:
            if not visit[j]:
                visit[j] = True
                kar.add(j)
                d.append(j)
    atumari.append(kar)
ans = 0
for i in range(len(atumari)):
    for j in atumari[i]:
        if p[j-1] in atumari[i]:
            ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
def main():
    def find(x):
        if par[x] < 0:
            return x
        else:
            par[x] = find(par[x])
            return par[x]

    def unite(x, y):
        x = find(x)
        y = find(y)
        if x == y:
            return False
        else:
            if par[x] > par[y]:
                x, y = y, x
            par[x] += par[y]
            par[y] = x
            return True

    def same(x, y):
        return find(x) == find(y)

    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    pdic = {e :0 for e in range(n)}
    for i, pe in enumerate(p):
        pdic[pe] = i

    par = [-1] * n
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x-1, y-1)

    r = 0
    for i1 in range(n):
        r += same(i1, pdic[i1+1])
    print(r)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
n,m=map(int,input().split())
p=list(map(int,input().split()))
uf=UnionFind(n)
for i in range(m):
  x,y=map(int,input().split())
  uf.union(x-1,y-1)
yes=[0]*n
for i in range(n):
  if uf.same(p[i]-1,i):
    yes[p[i]-1]=1
print(sum(yes))

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.root = list(range(n + 1))
        self.size = [1] * (n + 1)

    def find(self, x):
        root = self.root
        while root[x] != x:
            root[x] = root[root[x]]
            x = root[x]
        return x

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        sx, sy = self.size[x], self.size[y]
        if sx < sy:
            self.root[x] = y
            self.size[y] += sx
        else:
            self.root[y] = x
            self.size[x] += sy


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


uf = UnionFind(n)
union = uf.union
find = uf.find


for _ in range(m):
    x, y = map(int, input().split())
    union(x - 1, y - 1)

ans = 0
for i, x in enumerate(p):
    if find(i) == find(x - 1):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7) #再帰回数の上限を変更
N,M=map(int,input().split())
P=list(map(int,input().split()))
G=[[] for _ in range(N)]
for i in range(M):
    x,y=map(int,input().split())
    x-=1
    y-=1
    G[x].append(y)
    G[y].append(x)

chk=[0 for _ in range(N)]

for i in range(N):
    if P[i]==(i+1):
        chk[i]=1

def uni(v,G,cnt,C):
    C[v]=cnt
    for tmp in G[v]:
        if C[tmp]!=0:
            continue
        uni(tmp,G,cnt,C)

C=[0 for _ in range(N)]
cnt=1
ans=0
for i in range(N):
    if C[i]!=0:
        continue
    uni(i,G,cnt,C)
    cnt+=1

for i in range(N):
    p=P[i]
    if chk[p-1]:
        ans+=1
        continue
    else:
        num=i
        val=p
        if C[i]==C[p-1]:
            ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        # 負  : 根であることを示す。絶対値はランクを示す
        # 非負: 根でないことを示す。値は親を示す
        self.table = [-1] * n
 
    def _root(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self._root(self.table[x])
            return self.table[x]
 
    def find(self, x, y):
        return self._root(x) == self._root(y)
 
    def union(self, x, y):
        r1 = self._root(x)
        r2 = self._root(y)
        if r1 == r2:
            return
        # ランクの取得
        d1 = self.table[r1]
        d2 = self.table[r2]
        if d1 <= d2:
            self.table[r2] = r1
            if d1 == d2:
                self.table[r1] -= 1
        else:
            self.table[r1] = r2
 
 
if __name__ == '__main__':
    n,m=map(int,input().split())
    p=list(map(int,input().split()))
    g=UnionFind(n+1)
    for i in range(m):
        x,y=map(int,input().split())
        g.union(x,y)
    cnt=0
    l=[]*n
    for i,j in enumerate(p):
        if g.table[j]==-1:
            if i+1==j:
                cnt+=1
        else:
            if g.find(i+1,j):
                cnt+=1
    print(cnt)

Submission status: Accepted

Solution code:
inf = 10**18
mod = 10**9+7

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m = map(int, input().split())
p = list(map(int, input().split()))
uf = UnionFind(n)
for i in range(m):
    x,y = map(int, input().split())
    uf.union(x-1, y-1)
ans=0
for i,num in enumerate(p):
    if uf.same(i,num-1):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n, m = map(int, input().split())
p = list(map(int, input().split()))
union_find = UnionFind(n)
for _ in range(m):
    x, y = map(int, input().split())
    x -= 1
    y -= 1
    union_find.union(x, y)
res = 0
groups = {}
for i in range(n):
    x = union_find.find(i)
    if x not in groups:
        groups[x] = []
    groups[x].append(i)

for k, v in groups.items():
    idx_set = set(v)
    ps_set = set([p[i]-1 for i in v])
    res += len(idx_set-ps_set)
print(n-res)

Submission status: Accepted

Solution code:
from collections import deque
n,m,=map(int,input().split())
p=list(map(int,input().split()))
way=[[] for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    x-=1
    y-=1
    way[x].append(y)
    way[y].append(x)
ans=0
top=[False]*n
for i in range(n):
    l=deque([i])
    s=set([])
    t=set([])
    while l:
        now=l.popleft()
        for to in way[now]:
            if top[to]:
                continue
            else:
                top[to]=True
                l.append(to)
                s.add(to)
                t.add(p[to]-1)
    ans+=len(s&t)
cnt=0
for i in range(n):
    if top[i]:
        continue
    else:
        if i+1==p[i]:
            cnt+=1
print(ans+cnt)

Submission status: Accepted

Solution code:
# https://atcoder.jp/contests/arc097/tasks/arc097_b
# union-findらしい

n, m = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))

# xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)
    
    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

#xとyが同じ集合に属するかの判定
def same(x,y):
    return find(x) == find(y)

#xが属する集合の個数
def size(x):
    return -par[find(x)]

#初期化
#根なら-size,子なら親の頂点
par = [-1] * n

for _ in range(m):
    ai, bi = map(int, input().split())
    ai, bi = ai - 1 , bi - 1
    unite(ai, bi)

# print(par)
# print(P)

count = 0
for i in range(n):
    if same(i, P[i]):
        count += 1

print(count)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for i in range(m)]


class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


u = UnionFind(n)
for x, y in xy:
    u.union(x-1, y-1)

cnt = 0
for i, v in enumerate(p):
    if u.same(v-1, i):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
class UnionFind:

    # n要素で初期化
    def __init__(self,n):
        self.par = list(range(n))
        self.rank = [0]*n

    # 木の根を求める
    def find(self,x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]
    
    # xとyの属する集合を併合
    def unite(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return None
        
        if self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

    # xとyが同じ集合に属するか否か
    def same(self,x,y):
        return self.find(x) == self.find(y)

if __name__ == '__main__':
    n,m = map(int,input().split())
    p = list(map(int,input().split()))
    uf = UnionFind(n)
    for i in range(m):
        x,y = map(int,input().split())
        uf.unite(x-1,y-1)
    res = 0
    for i in range(n):
        if uf.same(i,p[i]-1):
            res += 1
    print(res)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def root(v):
    if v == par[v]:
        return v
    par[v] = root(par[v])
    return par[v]

def unite(u, v):
    u = root(u)
    v = root(v)
    if u == v:
        return
    if rank[u] < rank[v]:
        u, v = v, u
    par[v] = u
    if rank[u] == rank[v]:
        rank[u] += 1

def connected(u, v):
    return 1 if root(u) == root(v) else 0

N, M = map(int, input().split())
P = list(map(int, input().split()))
par = [i for i in range(N)]
rank = [0] * N
for _ in range(M):
    x, y = map(int, input().split())
    unite(x-1, y-1)
res = 0
for i in range(N):
    res += connected(i, P[i]-1)
print(res)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N,M = map(int, input().split())
    p_list = list(map(int, input().split()))

    uf = UnionFind(N)
    for i in range(M):
        x,y = map(int, input().split())
        uf.union(x-1,y-1)
        
    cnt = 0
    for i,p in enumerate(p_list):
        cnt += 1 if uf.same(p-1, i) else 0
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys
input = sys.stdin.readline

class UnionFind():
    def __init__(self, n, m = None, read = 0):
        self.n = n
        self.parents = [-1] * n
        if read:
            if m is None:
                exit(print("Warning: What is M"))
            for i in range(m):
                a, b = map(int, input().split())
                self.union(a - 1, b - 1)

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

n, m = map(int, input().split())
*p, = map(int, input().split())
UF = UnionFind(n, m, read = 1)

a = 0
for i in range(n):
    P = p[i] - 1
    if UF.same(P, i):
        a += 1
print(a)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,M=list(map(int,input().split()))
uf=UnionFind(N+1)
p=list(map(int,input().split()))
for i in range(M):
    x,y=list(map(int,input().split()))
    uf.union(x,y)
count=0
for i in range(1,N+1):
    if (uf.same(p[i-1],i)):count+=1
print(count)

Submission status: Accepted

Solution code:

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.parents = [-1] * n

  def find(self, x):
    if self.parents[x] < 0:
      return x
    else:
      self.parents[x] = self.find(self.parents[x])
      return self.parents[x]

  def union(self, x, y):
    x = self.find(x)
    y = self.find(y)

    if x == y:
      return

    if self.parents[x] > self.parents[y]:
      x, y = y, x

    self.parents[x] += self.parents[y]
    self.parents[y] = x

  def size(self, x):
    return -self.parents[self.find(x)]

  def same(self, x, y):
    return self.find(x) == self.find(y)

  def members(self, x):
    root = self.find(x)
    return [i for i in range(self.n) if self.find(i) == root]

  def roots(self):
    return [i for i, x in enumerate(self.parents) if x < 0]

  def group_count(self):
    return len(self.roots())

  def all_group_members(self):
    return {r: self.members(r) for r in self.roots()}

  def __str__(self):
    return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
  

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

uf = UnionFind(n)
for i in range(m):
  x,y = map(int, input().split())
  uf.union(x-1,y-1)
  
count = 0
for i in range(n):
  if uf.same(p[i]-1, i):
    count += 1
    
print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
        
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        
        if x == y:
            return
        
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def size(self, x):
        return -self.parents[self.find(x)]
        
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
    
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())
    
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
    
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    N, M = map(int, input().split())
    p = [int(i) - 1 for i in input().split()]
    uf = UnionFind(N)
    for _ in range(M):
        x, y = map(lambda i: int(i) - 1, input().split())
        uf.union(x, y)

    count = 0
    for i in range(N):
        if uf.same(i , p[i]):
            count += 1
    print(count)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

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

tree=UnionFind(N+1)

for _ in range(M):
    x,y=list(map(int,input().split()))

    tree.union(p[x-1],p[y-1])
ans=0

for i in range(1,N+1):
    if tree.same(i,p[i-1]):
        ans+=1

print(ans)

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self.par = [-1] * N

  def find(self, n):
    if self.par[n] < 0:
      return n
    else:
      self.par[n] = self.find(self.par[n])
      return self.par[n]

  def union(self, x,y):
    p1,p2 = self.find(x), self.find(y)
    if p1 == p2: return
    if p1 > p2:
      p1,p2 = p2,p1
    self.par[p1] += self.par[p2]
    self.par[p2] = p1

  def same(self, x,y):
    return self.find(x) == self.find(y)

N,M = map(int,input().split())
A = list(map(int,input().split()))
uf = UF(N+1)
for _ in range(M):
  u,v = map(int,input().split())
  uf.union(u,v)

res = 0
for i in range(N):
  if i+1 == A[i] or uf.same(i+1, A[i]):
    res += 1

print(res)

Submission status: Accepted

Solution code:
#!/usr/bin python3
# -*- coding: utf-8 -*-

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def find(self, x):          #親を出力
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def same(self, x, y):       #xとyが同じグループかどうか
        return self.find(x) == self.find(y)

    def size(self, x):          #グループの要素数
        return -self.parents[self.find(x)]

    def members(self, x):       #xと同じグループの要素
        root = self.find(x)
        return {i for i in range(self.n) if self.find(i) == root}

    def roots(self):            #親の要素一覧
        return {i for i, x in enumerate(self.parents) if x < 0}

    def group_count(self):      #グループの個数
        return len(self.roots())

    def all_group_members(self):      #グループのメンバー一覧
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

################

def main():
    N, M = map(int, input().split())
    P = list(map(int,input().split()))
    uf = UnionFind(N)
    for i in range(M):
        a,b = map(int,input().split())
        uf.union(a-1, b-1)

    ret = 0
    for i in range(N):
        if uf.same(P[i]-1, i):
            ret += 1
    print(ret)

if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            # 経路圧縮
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    
    def same(self, x, y):
        return self.find(x) == self.find(y)

N,M = map(int,input().split())
p = list(map(int,input().split()))
uf = UnionFind(N)
count = 0

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

for i in range(N):
    if uf.same(i, p[i]-1):
        count += 1

print(count)

Submission status: Accepted

Solution code:
#!/usr/bin/env python3
import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())
nl = lambda: list(nm())
ns = lambda: sys.stdin.readline().rstrip()

N, M = nm()
P = nl()
assert len(P) == N
pairs = []
for i in range(M):
    x, y = nm()
    x -= 1
    y -= 1
    pairs.append((x, y))


def solve():
    uf = UnionFind(N)
    for (x, y) in pairs:
        uf.union(x, y)
    cnt = 0
    for i in range(N):
        if uf.same(P[i] - 1, i):
            cnt += 1
    return cnt


class UnionFind:
    def __init__(self, n):
        # total number of nodes.
        self.n = n
        # node id -> root node id
        self._root_table = list(range(n))
        # root node id -> group size
        self._size_table = [1] * n

    def find(self, x):
        """Returns x's root node id."""
        r = self._root_table[x]
        if r != x:
            # Update the cache on query.
            r = self._root_table[x] = self.find(r)
        return r

    def union(self, x, y):
        """Merges two groups."""
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        # Ensure that x is the larger (or equal) group.
        if self._size_table[x] < self._size_table[y]:
            x, y = y, x

        self._size_table[x] += self._size_table[y]
        self._root_table[y] = x

    def size(self, x):
        return self._size_table[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self._root_table) if x == i]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return "\n".join("{}: {}".format(r, self.members(r)) for r in self.roots())


if __name__ == "__main__":
    print(solve())

Submission status: Accepted

Solution code:
class UF():
  def __init__(self, N):
    self.parents = [-1] * (N+1)

  def union(self, f, t):
    p1 = self.find(f)
    p2 = self.find(t)
    if p1 == p2:
      return

    if self.parents[p1] > self.parents[p2]:
      p1,p2 = p2,p1
    self.parents[p1] += self.parents[p2]
    self.parents[p2] = p1

  def find(self, node):
    if self.parents[node] < 0:
      return node
    else:
      self.parents[node] = self.find(self.parents[node])
      return self.parents[node]

  def same(self, n1, n2):
    return self.find(n1) == self.find(n2)

N,M = map(int, input().split())
p = list(map(int, input().split()))
uf = UF(N)
xy = [ list(map(int, input().split())) for _ in range(M) ]

# for _ in range(M):
#   x,y = map(int, input().split())
#   uf.union(x,y)
for x,y in xy:
  uf.union(x,y)

res = 0
for i in range(N):
  if i+1 == p[i] or uf.same(i+1, p[i]):
    res += 1

print(res)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
p = [0] + list(map(int,input().split()))
l = [[] for _ in range(N+1)]
for i in range(M):
  x,y = map(int,input().split())
  l[x].append(y)
  l[y].append(x)

#unionfind
lp = [i for i in range(N+1)] #親のリスト
#木の根を求める
def root(x):
  if lp[x] == x:
    return x
  else:
    lp[x] = root(lp[x])
    return lp[x]
#xとyが同じ集合に属するか否か
def det(x,y):
  return root(x) == root(y)
#xとYが属する集合の併合 Yが親になる
def unite(x,y):
  x = root(x)
  y = root(y)
  if x != y:
    lp[x] = y 

seen = [False]*(N+1)
for i in range(1,N+1):
  if seen[i] == False:
    seen[i] = True
    d = deque([i])
    while len(d)>0:
      v = d.popleft()
      for j in l[v]:
        if seen[j] == False:
          seen[j] = True
          unite(j,i)
          d.append(j)
###
cnt = 0
for i in range(1,N+1):
  cnt += int(det(p[i],i))
print(cnt)