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:
class UnionFind:
    def __init__(self, N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1


N, M = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
UF = UnionFind(N)
for _ in range(M):
    x, y = map(lambda x: int(x) - 1, input().split())
    UF.union(x, y)
ans = 0
for i in range(N):
    if UF.find(P[i]) == UF.find(i):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = [int(i) for i in input().split()]
p_ls = [int(i) - 1 for i in input().split()]

par = [i for i in range(N)]
rank = [1 for i in range(N)]

def find(x):
    if par[x] == x:
        return x
    else:
        return find(par[x])

def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        pass
    else:
        if rank[x] > rank[y]:
            par[y] = x
            rank[x] += rank[y]
        else:
            par[x] = par[y]
            rank[y] += rank[x]

def is_same(x, y):
    if find(x) == find(y):
        return True
    else:
        return False

data_ls = list()
for i in range(M):
    x, y = [int(i)-1 for i in input().split()]
    if is_same(x, y):
        pass
    else:
        unite(x, y)
cnt = 0
for i in range(N):
    if is_same(i, p_ls[i]):
        cnt += 1
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n + 1)]
        self.rank = [0] * (n + 1)
        self.size = [1] * (n + 1)

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

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if self.rank[x] < self.rank[y]:
            if self.same_check(x, y) != True:
                self.size[y] += self.size[x]
                self.size[x] = 0
            self.par[x] = y
        else:
            if self.same_check(x, y) != True:
               self.size[x] += self.size[y]
               self.size[y] = 0
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
               self.rank[x] += 1

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


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

uf = UnionFind(N)
for i in range(M):
    x, y = list(map(int, input().split()))
    uf.union(x, y)

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

print(c)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,N):
        self.table = list(range(N))
        self.rank = [0] * N
        self.size = [1] * N
    
    def find(self,x):
        if self.table[x] == x:
            return x
        else:
            self.table[x] = self.find(self.table[x])
            return self.table[x]
    
    def unite(self,x,y):
        x,y = self.find(x),self.find(y)
        if x == y:
            return
        if self.rank[x] < self.rank[y]:
            self.table[x] = y
            self.size[y] += self.size[x]
        else:
            self.table[y] = x
            self.size[x] += self.size[y]
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    
    def same(self,x,y):
        return self.find(x) == self.find(y)
    
    def count(self,x):
        return self.size(x)

N,M = map(int,input().split())
P = list(map(int,input().split()))
uf = UnionFind(N)
for _ in range(M):
    x,y = map(int,input().split())
    uf.unite(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:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    # 検索
    def find(self, x):
        if self.par[x] == x:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        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

    # 同じ集合に属するか判定
    def same_check(self, x, y):
        return self.find(x) == self.find(y)

N, M = [int(x) for x in input().split()]

uf = UnionFind(N)
p = [int(x) for x in input().split()]
for m in range(M):
    x, y = [int(x) for x in input().split()]
    uf.union(x, y)

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

Submission status: Accepted

Solution code:
def f(r, a):
    if r[a] != a:
        r[a] = f(r, r[a])
    return r[a]


def union(r, x, y):
    a = f(r, x)
    b = f(r, y)
    if a != b:
        r[a] = b


n, m = list(map(int, input().split()))
p = list(map(int, input().split()))
r = [i for i in range(n)]

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


c = 0
for i in range(n):
    if f(r, i) == f(r, p[i] - 1):
        c += 1

print(c)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
par , rank = [],[] 

for i in range(n): 
    par.append(i)
    rank.append(0)

def find(x):
    if par[x] == x : return x
    else:
        par[x] = find(par[x])
        return par[x]

def unite(x,y): 
    x = find(x)
    y = find(y)
    if (x != y):
        if rank[x] < rank[y]:
            par[x] = y
        else :
            par[y] = x
            if (rank[x] == rank[y]) : rank[x] += 1

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

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

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

dic = {}

for i in range(n):
    i1 = find(i)
    if i1 in dic:
        dic[i1].append(i)
    else:
        dic[i1] = [i]
        

cnt = 0
for pp in list(dic):
    l = dic[pp]
    ll = []
    for i in l:
        ll.append(p[i]-1)
    for q in ll:
        if(par[q] == pp):cnt += 1
    
print(cnt)

Submission status: Accepted

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

class UnionFind:
    def __init__(self,n):
        self.par=[i for i in 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]
    def same_check(self,x,y):
        return self.find(x)==self.find(y)
    def union(self,x,y):
        x=self.find(x)
        y=self.find(y)
        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

uf=UnionFind(n)

for a,b in l:
    uf.union(a-1,b-1)

num=0
for i in range(n):
    num+=uf.same_check(i,p[i]-1)
print(num)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
rank = [0] * N
parent = [i for i in range(N)]

def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]
 
 
def same(x, y):
    return find(x) == find(y)
 
 
def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return
 
    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


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

# 一致している個数のカウント
num = 0
for i in range(N):
    num += same(i, P[i])
print(num)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
rank = [0] * N
parent = [i for i in range(N)]


def find(i):
    if parent[i] == i:
        return i
    else:
        parent[i] = find(parent[i])
        return parent[i]


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


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

    if rank[x] > rank[y]:
        parent[y] = x
    else:
        parent[x] = y
        if rank[x] == rank[y]:
            rank[y] += 1


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

num = 0
for i in range(N):
    num += same(i, P[i])

print(num)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank = [0] * size

    def root(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.root(self.parent[x])
        return self.parent[x]

    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)

        if x == y:
            return

        if self.rank[x] > self.rank[y]:
            self.parent[y] = x
        else:
            self.parent[x] = y
            if self.rank[x] == self.rank[y]:
                self.rank[y] += 1

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


def main():
    n, m = map(int, input().split())
    ps = list(map(int, input().split()))

    # 1-origin
    union_find = UnionFind(n + 1)
    for i in range(m):
        x, y = map(int, input().split())
        union_find.unite(x, y)

    ans = 0
    for key, value in enumerate(ps, 1):
        if union_find.same(key, value):
            ans += 1
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline
# -*- coding: utf-8 -*-


class UnionFind:
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

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

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

        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


N, M = map(int, input().split())
Un = UnionFind(N+1)
A = list(map(int, input().split()))

for _ in range(M):
    a, b = map(int, input().split())
    Un.union(a, b)

ans = 0
for i in range(N):
    if Un.same(A[i], i+1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
#ARC097-D
n,m=map(int,input().split())
P=list(map(int,input().split()))
edges=[list(map(int,input().split())) for _ in range(m)]

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

    def find(self,x):
        if self.par[x]==x:
            return x
        else:
            self.par[x]=self.find(self.par[x])
            return self.par[x]
    def union(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
        else:
            self.par[y]=x
            if self.rank[x]==self.rank[y]:
                self.rank[x]+=1
    def same_check(self,x,y):
        return self.find(x)==self.find(y)

uf=UnionFind(n)
ans=0
for i,j in edges:
    uf.union(i,j)
for i in range(n):
    if uf.same_check(i+1,P[i]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
class UnionFind:
    def __init__(self, n):
        self.p=[i for i in range(n)]
        self.r=[0 for i in range(n)]
    
    def root(self,x):
        if self.p[x]==x:
            return x
        else:
            self.p[x] = self.root(self.p[x])
            return self.p[x]
    
    def uni(self,x,y):
        x=self.root(x)
        y=self.root(y)
        if(x==y):
            return
        if self.r[x]<self.r[y]:
            self.p[x]=y
        else:
            self.p[y]=x
            if self.r[x]==self.r[y]:
                self.r[x]+=1
    
    def same(self,x,y):
        return self.root(x)==self.root(y)

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.uni(p[x-1]-1,p[y-1]-1)
count=0
for i in range(n):
    if uf.same(i,p[i]-1):
        count+=1
print(count)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)


class UnionFind(object):

    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        else:
            return False

N, M = map(int, input().split())
p = list(map(int, input().split()))
u = UnionFind(N+1)
for _ in range(M):
    x, y = map(int, input().split())
    u.union(x, y)

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

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
p = list(map(int,input().split()))
for i in range(n):
    p[i]-=1
####################################
#Union Find
par = [] #親
rank = [] #木の深さ

#初期化
for i in range(n):
    #par[i]:i rank[i]:0
    par.append(i)
    rank.append(0)

#木の根を求める
def find(x,par):
    if par[x] == x:
        return x
    else:
        return find(par[x],par)

#xとyの属する集合の併合
def unite(x,y,par,rank):
    x = find(x,par)
    y = find(y,par)
    
    if x != y:
        #xとyの属している集合が異なる時
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x]==rank[y]:
                rank[x] += 1

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



#######################################
for i in range(m):
    x,y = map(int,input().split())
    x -= 1
    y -=1
    unite(x,y,par,rank)

a = [[] for i in range(n)]
b = [[] for i in range(n)]
for i in range(n):
    k = find(i,par)
    a[k].append(i)
    b[k].append(p[i])

res = 0
for i in range(n):
    if len(a[i])!= 0 and len(b[i])!=0:
        res += len(set(a[i])&set(b[i]))
print(res)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
p = [int(i) for i in input().split()]
xy = []

for _ in range(M):
    xy.append(list(map(int,input().split())))

class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
    def root(self,a):
        if self.parent[a] == a:
            return a
        else:
            self.parent[a] = self.root(self.parent[a])
            return self.parent[a]
    def is_same(self,a,b):
        return self.root(a) == self.root(b)
    def unite(self,a,b):
        ra = self.root(a)
        rb = self.root(b)
        if ra == rb: return
        if self.rank[ra] < self.rank[rb]:
            self.parent[ra] = rb
        else:
            self.parent[rb] = ra
            if self.rank[ra] == self.rank[rb]: self.rank[ra] += 1

uf = UnionFind(N+1)
for x,y in xy:
    uf.unite(x,y)
count = 0
for i in p:
    if uf.is_same(i,p[i-1]):
        count += 1
print(count)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
p = [int(i) for i in input().split()]
xy = []

for _ in range(M):
    xy.append(list(map(int,input().split())))

par = [0 for _ in range(N+1)]
rank = [0 for _ in range(N+1)]

def init(n):
    for i in range(n):
        par[i] = i
        rank[i] = 0
def find(x):
    if par[x] ==x:
        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
    if rank[x] < rank[y]:
        par[x] = y
    else:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1

def same(x,y):
    return True if find(x) == find(y) else False

init(N+1)
for x,y in xy:
    unite(x,y)
count = 0
for i in p:
    if same(i,p[i-1]):
        count += 1
print(count)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
par=[0 for i in range(N)]
rnk=[0 for i in range(N)]
def init(n):
    for i in range(N):
        par[i]=i
        rnk[i]=0
def find(x):
    if par[x]==x:
        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
    if (rnk[x]<rnk[y]):
        par[x]=y
    else:
        par[y]=x
        if(rnk[x]==rnk[y]):
            rnk[x]+=1
def same(x,y):
    return find(x)==find(y)

p=[int(i)-1 for i in input().split()]
init(N)
for i in range(M):
    x,y=map(int,input().split())
    unite(x-1,y-1)
ans=0
for i in range(N):
    if same(i,p[i]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:
N, M = [int(_) for _ in input().split()]
P = [0] + [int(_) for _ in input().split()]
XY = [[int(_) for _ in input().split()] for _ in range(M)]

UF = list(range(N + 1))


def find(x):
    if UF[x] != x:
        UF[x] = find(UF[x])
    return UF[x]


def unite(x, y):
    UF[find(x)] = find(y)


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


for x, y in XY:
    unite(x, y)

ans = 0
for i in range(1, N + 1):
    if same(i, P[i]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
P = [int(p) for p in input().split()]

Par = [int(i) for i in range(N+1)]
Rank = [0 for i in range(N+1)]

def find(i, Par):
    if Par[i] == i:
        return i
    else:
        Par[i] = find(Par[i], Par)
        return Par[i]
def Unite(x, y):
    rx, ry = find(x, Par), find(y, Par)
    if rx == ry: return
    if Rank[rx] < Rank[ry]: Par[rx] = ry
    else: 
        Par[ry] = rx
        if Rank[rx] == Rank[ry]: Rank[rx] += 1
def Same(x, y): return find(x, Par) == find(y, Par)
    

for i in range(M):
    x, y = map(int, input().split())
    x, y = min(x, y), max(x, y)
    Unite(x, y)
    
Count = 0
for i in range(N):
    Count += (1 if Same(P[i], i+1) else 0)
print(Count)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, n=1):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(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]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x != y:
            if self.rank[x] < self.rank[y]:
                x, y = y, x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.par[y] = x

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

n,m=map(int, input().split())
p=list(map(int, input().split()))
uf1=UnionFind(n)
for i in range(m):
    a,b=map(int, input().split())
    uf1.union(a-1,b-1)
count=0
for i in range(n):
    if uf1.is_same(i,p[i]-1):count+=1
print(count)

Submission status: Accepted

Solution code:
def inpl(): return [int(i) for i in input().split()]
class UnionFind():
    def __init__(self, num):
        self.par = [-1 for _ in range(num)]
    
    def find(self, x):
        if self.par[x] < 0:
            return x
        else:
            x = self.par[x]
            return self.find(x)
    
    def union(self, x, y):
        rx = self.find(x)
        ry = self.find(y)
        if rx != ry:
            if self.par[rx] < self.par[ry]:
                self.par[ry] = rx
            if self.par[rx] > self.par[ry]:
                self.par[rx] = ry
            else:
                self.par[rx] -= 1
                self.par[ry] = rx
        return

from collections import defaultdict
H = defaultdict(lambda: set([]))
H1 = defaultdict(lambda: set([]))
N, M = inpl()
p = inpl()
deer = UnionFind(N)
for _ in range(M):
    x, y = inpl()
    deer.union(x-1,y-1)

for i in range(N):
    H[deer.find(i)].add(i+1)
    H1[deer.find(i)].add(p[i])
    
ans =0
for i in H:
    ans += len(H[i] & H1[i])
print(ans)

Submission status: Accepted

Solution code:
#!/usr/bin/env python


class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(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]

    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
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


n, m = map(int, input().split())
ps = list(map(int, input().split()))
uf = UnionFind(n + 1)
for _ in range(m):
    x, y = map(int, input().split())
    uf.unite(x, y)
print(sum([uf.same(i + 1, p) for i, p in enumerate(ps)]))

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-

class UnionFind():
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.rank = [0 for _ in range(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]

    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
        else:
            self.par[y] = x
            if self.rank[x]==self.rank[y]:
                self.rank[x] += 1

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

n,m = map(int, input().split())
p = [int(x) for x in input().split()]
uf = UnionFind(n+1)
for _ in range(m):
    x,y = map(int, input().split())
    uf.unite(x,y)

cnt = 0
for i in range(1,n+1):
    if uf.same(i,p[i-1]):
        cnt += 1

print(cnt)

Submission status: Accepted

Solution code:
N,M = map(int,input().split())
p = [i-1 for i in map(int,input().split())]
swap = []
for j in range(M):
    swap.append([i-1 for i in map(int,input().split())])


# 0からn-1まで
n = N

#初期化
par = []
rank = []
for i in range(n):
    par.append(i) # par[i]==iの時root
    rank.append(0) # 深さ
    
def find(x): # rootの探索&縮約
    if par[x]==x:
        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
    elif rank[x]<rank[y]:
        par[x]=y
    else:
        par[y]=x
        if rank[x]==rank[y]:
            rank[x] += 1

for s in swap:
    unite(s[0],s[1])


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

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

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
P = list(map(int, input().split()))
par = list(range(N))

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

def unite(x, y):
    x, y = find(x), find(y)
    if x != y:
        par[y] = x

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

place = {v - 1: i for i, v in enumerate(P)}
ans = 0
for i, v in enumerate(P):
    if find(i) == find(place[i]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
p = list(map(int,input().split()))
p.insert(0,0)
def find(A,x):
  p = A[x]
  if p == x:
    return x
  else:
    A[x] = find(A,p)
    return A[x]
  
def union(A,x,y):
  rx = find(A,x)
  ry = find(A,y)
  A[ry] = rx
  A[y] = rx
  
def same(A,x,y):
  return find(A,x) == find(A,y)

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

Submission status: Accepted

Solution code:
f = lambda: map(int,input().split())


class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[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.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


n,m = f()
p = list(f())

u = UnionFind(n)
for _ in range(m):
    x,y = f()
    u.unite(x-1, y-1)


ans = 0
for i in range(n):
    if u.find(i)==u.find(p[i]-1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
f = lambda: map(int,input().split())


class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.rank = [0 for _ in range(size)]

    def find(self, x):
        if self.parent[x] == x:
            return x
        else:
            return self.find(self.parent[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.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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


n,m = f()
p = list(f())

u = UnionFind(n)
for _ in range(m):
    x,y = f()
    u.unite(x-1, y-1)

gnum = [set() for _ in range(n)]
pnum = [set() for _ in range(n)]
for i in range(n):
    root = u.find(i)
    gnum[root].add(i)
    pnum[root].add(p[i]-1)
ans = 0
for i in range(n):
    ans += len(gnum[i]&pnum[i])
print(ans)

Submission status: Accepted

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**15
mod = 10**9+7

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
def pf(s): return print(s, flush=True)


class UnionFind:
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]

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

    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    def subsetall(self):
        a = []
        for i in range(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

def main():
    n,m = LI()
    p = LI_()
    a = [LI_() for _ in range(m)]
    uf = UnionFind(n)
    for x,y in a:
        uf.union(x,y)
    r = 0
    for i in range(n):
        if uf.find(i) == uf.find(p[i]):
            r += 1

    return r



print(main())

Submission status: Accepted

Solution code:
from collections import deque

N, M = map(int, input().split())
P = list(map(int, input().split()))
G = [[] for i in range(N)]
check, group = [0 for j in range(N)], [-1 for k in range(N)]


def bfs(s, no):
    check[s] = group[P[s]] = no
    q = deque()
    q.append(s)

    while len(q) != 0:
        u = q.popleft()
        for v in G[u]:
            if check[v] == 0:
                check[v] = no
                group[P[v]] = no
                q.append(v)


def main():
    for i in range(M):
        x, y = map(int, input().split())
        G[x-1].append(y-1)
        G[y-1].append(x-1)

    for i in range(N):
        P[i] -= 1

    cnt = 1
    for i in range(N):
        if check[i] == 0:
            bfs(i, cnt)
            cnt += 1

    ans = 0
    for i in range(N):
        if check[i] == group[i]:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()