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.

Solution (Python):
def main():
    cnt = 0
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i in range(1, n+1):
        if same(i, p[i-1]):
            cnt += 1
    print(cnt)

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

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

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

if __name__ == "__main__":
    n, m = map(int, input().split())
    par = list(range(n+1))
    p = list(map(int, input().split()))
    main()

Solution (Python):
def main():
    cnt = 0
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i in range(1, n+1):
        if same(i, p[i-1]):
            cnt += 1
    print(cnt)

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

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

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

if __name__ == "__main__":
    n, m = map(int, input().split())
    par = list(range(n+1))
    p = list(map(int, input().split()))
    main()

Solution (Python):
def main():
    p = [0] + list(map(int, input().split()))
    cnt = 0
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i in range(1, n+1):
        if same(i, p[i]):
            cnt += 1
    print(cnt)

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

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

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

if __name__ == "__main__":
    n, m = map(int, input().split())
    par = list(range(n+1))
    main()

Solution (Python):
def main():
    cnt = 0
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i in range(1, n+1):
        if same(i, p[i-1]):
            cnt += 1
    print(cnt)
        
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

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

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

if __name__ == "__main__":
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    par = [0] + [i for i in range(1, n+1)]
    main()

Solution (Python):
def main():
    p = [0] + list(map(int, input().split()))
    cnt = 0
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i in range(1, n+1):
        if same(i, p[i]):
            cnt += 1
    print(cnt)

def root(x):
    if parent[x] == x:
        return x
    parent[x] = root(parent[x])
    return parent[x]

def unite(x, y):
    root_x = root(x)
    if root_x != root(y):
        parent[root_x] = y

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

if __name__ == "__main__":
    n, m = map(int, input().split())
    parent = list(range(n+1))
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = [0] + list(map(int, input().split()))
    cnt = 0
    global parent
    parent = list(range(n+1))
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i in range(1, n+1):
        if same(i, p[i]):
            cnt += 1
    print(cnt)

def root(x):
    if parent[x] == x:
        return x
    parent[x] = root(parent[x])
    return parent[x]

def unite(x, y):
    root_x = root(x)
    if root_x != root(y):
        parent[root_x] = y

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

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = [0] + list(map(int, input().split()))
    cnt = 0
    global parent
    parent = list(range(n+1))
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i in range(1, n+1):
        if root(i) == root(p[i]):
            cnt += 1
    print(cnt)

def root(x):
    if parent[x] == x:
        return x
    parent[x] = root(parent[x])
    return parent[x]

def unite(x, y):
    root_x = root(x)
    if root_x != root(y):
        parent[root_x] = y

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = [0] + list(map(int, input().split()))
    cnt = 0
    global parent
    parent = list(range(n+1))
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i in range(1, n+1):
        cnt += (root(i) == root(p[i]))
    print(cnt)

def root(x):
    if parent[x] == x:
        return x
    parent[x] = root(parent[x])
    return parent[x]

def unite(x, y):
    root_x = root(x)
    if root_x != root(y):
        parent[root_x] = y

if __name__ == "__main__":
    main()

Solution (Python):
def main():
    cnt = 0
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i in range(1, n+1):
        if same(i, p[i-1]):
            cnt += 1
    print(cnt)
        
def root(x):
    if par[x] == x:
        return x
    par[x] = root(par[x])
    return par[x]

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

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

if __name__ == "__main__":
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    par = [0] + [i for i in range(1, n+1)]
    main()

Solution (Python):
class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def main():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    xy = [list(map(int, input().split())) for _ in range(m)]
    tree = UnionFind(n)
    for x, y in xy:
        tree.Unite(x, y)

    root = [[] for _ in range(n+1)]
    f_root = []
    for i in range(n):
        x = tree.Find_Root(p[i])
        root[x].append(i+1)
        f_root.append(x)
    out_put = 0
    for i in range(n):
        if f_root[i]==f_root[p[i]-1]:
            out_put += 1
    print(out_put)

if __name__=="__main__":
    main()

Solution (Python):
class UnionFind():
    
    
    def __init__(self, n):
        self.n = n
        
        
        self.root = [-1]*(n+1)
        
        self.rnk = [0]*(n+1)

    
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    
    def Unite(self, x, y):
        
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        
        if(x == y):
            return 
        
        elif(self.rnk[x] > self.rnk[y]):
            self.root[x] += self.root[y]
            self.root[y] = x

        else:
            self.root[y] += self.root[x]
            self.root[x] = y
            
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    
    def Count(self, x):
        return -self.root[self.Find_Root(x)]


def main():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    xy = [list(map(int, input().split())) for _ in range(m)]
    tree = UnionFind(n)
    for x, y in xy:
        tree.Unite(x, y)

    root = [[] for _ in range(n+1)]
    f_root = []
    for i in range(n):
        x = tree.Find_Root(p[i])
        root[x].append(i+1)
        f_root.append(x)
    out_put = 0
    for i in range(n):
        if f_root[i]==f_root[p[i]-1]:
            out_put += 1
    print(out_put)

if __name__=="__main__":
    main()

Solution (Python):
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) 

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

print(cnt)

Solution (Python):

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)



def size(x):
    return -par[find(x)]



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

Solution (Python):
N, M = map(int, input().split())
par = [i for i in range(N)]
rank = [0 for _ in range(N)]

def root(x):
  if par[x] == x:
    return x
  else:
    par[x] = root(par[x])
    return par[x]
def unite(x, y):
  s, t = root(x), root(y)
  if s != t:
    if rank[s] < rank[t]:
      par[s] = t
    else:
      par[t] = s
      if rank[s] == rank[t]:
        rank[s] += 1
        
p = list(map(int, input().split()))
for i in range(N):
  p[i] -= 1
for i in range(M):
  x, y = map(int, input().split())
  unite(x-1, y-1)
for i in range(N):
  par[i] = root(i)
cnt = 0
for i in range(N):
  if par[i] == par[p[i]]:
    cnt += 1
print(cnt)

Solution (Python):
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 __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N, M = map(int, input().split())
uf = UnionFind(N)
P = list(map(int, input().split()))
ans = 0
for i in range(M):
    A, B = list(map(int, input().split()))
    uf.union(A-1,B-1)
for i in range(N):
    if uf.same(P[i]-1,i):
        ans += 1
print(ans)

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

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



G = [[] for _ in range(N+1)]
for el in xy:
    x, y = el
    G[x].append(y)
    G[y].append(x)


seen=[False] * (N+1)
def dfs(n):
    seen[n]=True
    group[-1].append(n)
    for child in G[n]:
        if seen[child] == False:
            dfs(child)

group=[]
for i in range(1,N+1):
    if seen[i] == False:
        group.append([])
        dfs(i)
        



cnt = 0
for el in group:
    temp = set(el) & set([p[i-1] for i in el])
    cnt += len(temp)
print(cnt)

Solution (Python):
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 in range(n):
    if uf.same(i,p[i]-1):
        ans+=1
print(ans)

Solution (Python):
NN = 202020
MOD = 10**9+7
INF = float("inf")


class UnionFind2:
    def __init__(self, n):
        self.par = [i for i in range(n)]
        self.size = [1] * 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):
        if self.same(x, y):
            return
        else:
            parx, pary = self.find(x), self.find(y)
            self.size[pary] += self.size[parx]
            self.size[parx] = 0
            self.par[parx] = pary

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

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


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

T = UnionFind2(n)

for i in range(m):
    T.unite(S[i][0]-1, S[i][1]-1)

print(sum([T.same(i, A[i]-1) for i in range(n)]))

Solution (Python):
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.par=[i for i in range(n)]
        self.size=[0 for i in range(n)]
    def find(self,x):
        if x==self.par[x]:
            return x
        self.par[x]=self.find(self.par[x])
        return self.par[x]
    def merge(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if x==y:
            return
        if self.size[x]>=self.size[y]:
            self.par[y]=x
            self.size[x]+=self.size[y]
        else:
            self.par[x]=y
            self.size[y]+=self.size[x]
    def same(self,x,y):
        x=self.find(x)
        y=self.find(y)
        return x==y
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.merge(x-1,y-1)
ans=0
for i in range(n):
    if p[i]-1==i or uf.same(i,p[i]-1):
        ans+=1
print(ans)

Solution (Python):
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 unite(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 -size.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=list(map(int,input().split()))
uf=UnionFind(n)
for _ in range(m):
  x,y=map(int,input().split())
  uf.unite(x-1,y-1)
ans=0
for i in range(n):
  if p[i]-1==i or uf.same(i,p[i]-1):
    ans+=1
print(ans)

Solution (Python):
class UnionFind:
    def __init__(self,n):
        super().__init__()
        self.par = [-1]*n
        self.rank = [0]*n
        self.tsize = [1]*n

    
    def root(self,x):
        if self.par[x] == -1:
            return x 
        else:
            self.par[x] = self.root(self.par[x])
            return self.par[x]

    def unite(self, x, y):
        x_r = self.root(x)
        y_r = self.root(y)
        
        if self.rank[x_r]>self.rank[y_r]:
            self.par[y_r] = x_r

        elif self.rank[x_r]<self.rank[y_r]:
            self.par[x_r] = y_r

        elif x_r != y_r:
            self.par[y_r] = x_r
            self.rank[x_r] += 1

        if x_r != y_r:
            size = self.tsize[x_r]+self.tsize[y_r]
            self.tsize[x_r] = size
            self.tsize[y_r] = size

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

    def size(self,x):
        return self.tsize[self.root(x)]

def main():

    n,m = tuple([int(t)for t in input().split()])
    p = tuple([int(t)-1 for t in input().split()])

    uf = UnionFind(n)
    for _ in [0]*m:
        uf.unite(*[int(t)-1 for t in input().split()])

    ans = 0
    for i in range(n):
        if uf.isSame(i,p[i]):
            ans += 1

    print(ans)
if __name__ == "__main__":
    main()

Solution (Python):
n,m = map(int,input().split())
f = lambda x : int(x) - 1
p = list(map(f,input().split()))
par = [i for i in range(n)]

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

def unite(x,y):
    rx = root(x)
    ry = root(y)
    if rx != ry:
        par[rx] = ry

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

ans = 0
for i in range(n):
    if root(i) == root(p[i]): ans += 1

print(ans)

Solution (Python):
n,m = map(int,input().split())
f = lambda x : int(x) - 1
p = list(map(f,input().split()))
par = [i for i in range(n)]

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

def unite(x,y):
    if root(x) == root(y):
        return
    else:
        par[root(x)] = root(y)

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

ans = 0
for i in range(n):
    if root(i) == root(p[i]): ans += 1

print(ans)

Solution (Python):
class UnionFind:
    def __init__(self, n=1):
        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 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.parent[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()))
uf = UnionFind(N)
for i in range(M):
  x, y = map(int, input().split())
  uf.union(x-1, y-1)

for i in range(N):
  uf.find(i)

ans = 0
for _p in p:
  ans += uf.is_same(_p-1, p[_p-1]-1)

print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = list(range(n))
        self.rank = [1]*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 unit(self,x,y):
        x, y = self.find(x), self.find(y)
        if x==y: return
        if self.rank[x] < self.rank[y]:
            x,y = y,x
        self.rank[x] += self.rank[y]
        self.par[y] = x
        
n,m,*pxy = map(int,open(0).read().split())
p = pxy[:n]
xy = pxy[n:]

uf = UnionFind(n)

for x,y in zip(xy[::2],xy[1::2]):
    uf.unit(x-1,y-1)

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

print(ans)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.root = [-1]*(n+1)
        self.rnk = [0]*(n+1)
    def Find_Root(self, x):
        if(self.root[x] < 0):
            return x
        else:
            self.root[x] = self.Find_Root(self.root[x])
            return self.root[x]
    def Unite(self, x, y):
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        if(x == y):
            return 
        if self.root[x] > self.root[y]:
            x, y = y, x
        self.root[x] += self.root[y]
        self.root[y] = x 
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)
    def Count(self, x): 
        return -self.root[self.Find_Root(x)]
    def Members(self, x): 
        return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
    def Roots(self): 
        return [i for i, x in enumerate(self.root) if x < 0]
    def Group_Count(self): 
        return len(self.Roots())

n, m = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(m)]
uf = UnionFind(n+1)
for x, y in xy:
    uf.Unite(p[x-1], p[y-1])
ans = 0
for i in range(n):
    if uf.isSameGroup(i+1, p[i]):
        ans += 1
print(ans)

Solution (Python):
import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
p = [int(x) for x in input().split()]


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)


def size(x):
    return -par[find(x)]



par = [-1]*n


for _ in range(m):
    a, b = [int(x) for x in input().split()]
    unite(a - 1, b - 1)

ans = 0

for i, j in enumerate(p):
    if same(i, j - 1):
        ans += 1

print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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 unite(self, x, y):
        """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):
        """xとyが同じ集合に属するか否か"""
        return self.find(x) == self.find(y)

    def size(self, x):
        """グループのサイズを返す"""
        return -self.parents[self.find(x)]

N , M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]
uf = UnionFind(N)
for x, y in xy:
    uf.unite(x - 1, y - 1)
ans = 0

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

print(ans)

Solution (Python):

n, m = map(int, input().split())
p = [int(x)-1 for x in input().split()]


par=[i for i in range(n)]
size=[1 for _ in range(n)]
rank=[0 for _ in range(n)]

def find(x):
    if par[x]==x:
        return x
    else:
        par[x]=find(par[x])
        return par[x]
    
def merge(x,y):
    x=find(x)
    y=find(y)
    if x==y:
        return
    
    if rank[x]>rank[y]:
        par[y]=x
        size[x]+=size[y]
    else:
        par[x]=y
        size[y]+=size[x]
        if rank[x]==rank[y]:
            rank[y]+=1
            
def same(x,y):
    return find(x)==find(y)

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

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

Solution (Python):




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

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

def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if(x == y):
        return 0

    if rank[x] < rank[y]:
        par[x] = y

        temp = size[x] * size[y]
        size[y] = size[x] + size[y]
    else:
        par[y] = x
        if (rank[x] == rank[y]):
            rank[x] += 11

        temp = size[x] * size[y]
        size[x] = size[x] + size[y]
    return temp

def is_same(x,y):
    return find_root(x) == find_root(y)


par = list(range(n))
rank = [0]*n
size = [1]*n

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

edges = [list(map(int, input().split())) for _ in range(m)]
edges = [[b[0]-1, b[1]-1] for b in edges] 

for b in range(m):
    unite(edges[b][0] , edges[b][1])

ans = 0
for i in range(n):
    num = init_nums[i]
    
    if is_same(i, num - 1):
        ans += 1

print(ans)

Solution (Python):


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

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

def unite(x, y):
    x = find_root(x)
    y = find_root(y)
    if(x == y):
        return 0

    if rank[x] < rank[y]:
        par[x] = y

        temp = size[x] * size[y]
        size[y] = size[x] + size[y]
    else:
        par[y] = x
        if (rank[x] == rank[y]):
            rank[x] += 11

        temp = size[x] * size[y]
        size[x] = size[x] + size[y]
    return temp

def is_same(x,y):
    return find_root(x) == find_root(y)


par = list(range(n))
rank = [0]*n
size = [1]*n

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

edges = [list(map(int, input().split())) for _ in range(m)]
edges = [[b[0]-1, b[1]-1] for b in edges] 

for b in range(m):
    unite(edges[b][0] , edges[b][1])




ans = 0
for i in range(n):
    num = init_nums[i]
    
    if is_same(i, num - 1):
        ans += 1

arr = [0] * n
for i in range(n):
    arr[i] = find_root(i)

print(ans)

Solution (Python):
n, m = map(int, input().split())
p = list(map(int, input().split()))
XY = [ map(int, input().split()) for _ in range(m) ]

class UnionFind:
    def __init__(self, n):
        self.table = [-1 for _ in range(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

uf = UnionFind(n)
for (x, y) in XY:
    uf.union(x-1, y-1)
cnt = 0
for i in range(n):
    if uf.find(i, p[i]-1): cnt += 1
print(cnt)

Solution (Python):
n, m = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
xy = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

parents = [i for i in range(n)]
ranks = [0 for _ in range(n)]


def root(x):
    return x if x == parents[x] else root(parents[x])


def is_same(x, y):
    return root(x) == root(y)


def unite(x, y):
    x, y = root(x), root(y)
    if x == y:
        return
    if ranks[x] < ranks[y]:
        parents[x] = y
        if ranks[x] == ranks[y]:
            ranks[y] += 1
    else:
        parents[y] = x
        if ranks[x] == ranks[y]:
            ranks[x] += 1


for x_, y_ in xy:
    unite(x_, y_)

cnt = sum((1 if is_same(i, p_) else 0) for i, p_ in enumerate(p))
print(cnt)

Solution (Python):
n, m = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
xy = [list(map(lambda x: int(x) - 1, input().split())) for _ in range(m)]

parents = [i for i in range(n)]
ranks = [0 for _ in range(n)]


def root(x):
    return x if x == parents[x] else root(parents[x])


def is_same(x, y):
    return root(x) == root(y)


def unite(x, y):
    x, y = root(x), root(y)
    if x == y:
        return
    if ranks[x] < ranks[y]:
        parents[x] = y
    else:
        parents[y] = x
        if ranks[x] == ranks[y]:
            ranks[x] += 1


for x_, y_ in xy:
    unite(x_, y_)

cnt = sum((1 if is_same(i, p_) else 0) for i, p_ in enumerate(p))
print(cnt)