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):
import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def mt(f):
    import time
    import sys

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        print(e - s, 'sec', file=sys.stderr)
        return ret

    return wrap


class UnionFind():
    def __init__(self):
        self.__table = {}

    def __root(self, x):
        if x not in self.__table:
            self.__table[x] = x
        elif x != self.__table[x]:
            self.__table[x] = self.__root(self.__table[x])

        return self.__table[x]

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

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

        if x != y:
            self.__table[x] = y


@mt
def slv(N, M, P, XY):
    P = [-1] + P
    

    uf = UnionFind()
    for x, y in XY:
        uf.union(x, y)

    ans = 0
    for i, p in enumerate(P):
        if uf.same(p, i):
            ans += 1

    return ans


def main():
    N, M = read_int_n()
    P = read_int_n()
    XY = []
    for _ in range(M):
        XY.append(read_int_n())

    print(slv(N, M, P, XY))


if __name__ == '__main__':
    main()

Solution (Python):
import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def mt(f):
    import time
    import sys

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        print(e - s, 'sec', file=sys.stderr)
        return ret

    return wrap


def root(G, x):
    if G[x] != x:
        G[x] = root(G, G[x])
    return G[x]


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


def union(G, x, y):
    x = root(G, x)
    y = root(G, y)

    if x != y:
        G[x] = y


@mt
def slv(N, M, P, XY):
    P = [-1] + P
    G = [i for i in range(N + 1)]

    for x, y in XY:
        union(G, x, y)

    ans = 0
    for i, p in enumerate(P):
        if same(G, p, i):
            ans += 1

    return ans


def main():
    N, M = read_int_n()
    P = read_int_n()
    XY = []
    for _ in range(M):
        XY.append(read_int_n())

    print(slv(N, M, P, XY))


if __name__ == '__main__':
    main()

Solution (Python):
N, M = map(int, input().split())
P = list(map(int, input().split()))

parent = list(range(N))
rank = [0] * N

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


def getRoot(x):
  p = parent[x]
  if p == x:
    return p
  ret = getRoot(p)
  parent[x] = ret
  return ret

def join(x, y):
  rx = getRoot(x)
  ry = getRoot(y)
  if rank[rx] < rank[ry]:
    parent[rx] = ry
  else:
    parent[ry] = rx
    if rank[rx] == rank[ry]:
      rank[rx] += 1

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

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

print(ans)

Solution (Python):
n, m = map(int, input().split())
p = list(map(int, input().split()))
g = [[] for _ in range(n+1)]
for _ in range(m):
    x, y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)
s = [0]*(n+1)
r = 0
for i, j in enumerate(p, 1):
    q = [i]
    for k in q:
        if s[k]:
            continue
        s[k] = i
        q.extend(g[k])
    r += s[j] == s[i]
print(r)

Solution (Python):
def root(x, parent_list):
    if parent_list[x] == x:
        return parent_list[x]
    else:
        parent_list[x] = root(parent_list[x], parent_list)
        return parent_list[x]


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


def unite(x, y, parent_list):
    x = root(x, parent_list)
    y = root(y, parent_list)
    if x == y:
        return

    parent_list[x] = y

N, M = [int(elem) for elem in input().split(' ')]
p_list = [int(elem) - 1 for elem in input().split(' ')]

swap_list = [[int(elem) - 1 for elem in input().split(' ')]\
            for _ in range(M)]

parent_list = list(range(N))
for swap in swap_list:
    unite(swap[0], swap[1], parent_list)

count = 0
for i in range(N):
    if root(p_list[i], parent_list) == root(i, parent_list):
        count += 1

print(count)

Solution (Python):
N, M = map(int, input().split())
*P, = map(int, input().split())
*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    y = p[x] = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1

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

pp = [set() for i in range(N)]
qq = [set() for i in range(N)]
for i in range(N):
    r = root(i)
    pp[r].add(i)
    qq[r].add(P[i]-1)

ans = 0
for i in range(N):
    ans += len(pp[i] & qq[i])
print(ans)

Solution (Python):
n,m = map(int,input().split())
p = list(map(int, input().split()))
g = [[] for _ in range(0,n+1)]
visit = [None] * (n+1)
ans = 0
for _ in range(0,m):
    x,y = map(int, input().split())
    g[x].append(y)
    g[y].append(x)
for i in range(1,n+1):
    if visit[i] is not None:
        continue
    stack = [i]
    part = [i]
    visit[i] = 0
    while len(stack) > 0:
        q = stack.pop()
        for qq in g[q]:
            if visit[qq] is None:
                visit[qq] = 0
                part.append(qq)
                stack.append(qq)
    part2 = []
    for i in part:
        part2.append(p[i-1])
    ans += len(list(set(part) & set(part2)))
print(ans)

Solution (Python):



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

    
    def find(self,x):
        while self.table[x] >= 0:
            
            x = self.table[x]
        return x

    
    def union(self,x,y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] != self.table[s2]:
                if self.table[s1] < self.table[s2]:
                    self.table[s2] = s1
                else:
                    self.table[s1] = s2
            else:
                
                
                self.table[s1] += -1
                self.table[s2] = s1
        return
    
n,m = list(map(int,input().split()))
pp = list(map(int,input().split()))
p = [i-1 for i in pp]


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

print(c)

Solution (Python):
def main():
    n, m = map(int, input().split())
    p = map(int, input().split())
    trans = []

    for _ in range(m):
        x, y = map(int, input().split())
        trans.append((x, y))
    
    ss = dict()

    for t in trans:
        x, y = t
        xs = ss.get(x, None)
        ys = ss.get(y, None)

        if xs is None and ys is None:
            zs = set([x, y])
            ss[x] = zs
            ss[y] = zs
        elif xs is not None and ys is None:
            xs.add(y)
            ss[y] = xs
        elif xs is None and ys is not None:
            ys.add(x)
            ss[x] = ys
        else:
            if id(xs) == id(ys):
                continue

            if len(xs) >= len(ys):
                for yy in ys:
                    ss[yy] = xs
                    xs.add(yy)
            else:
                for xx in xs:
                    ss[xx] = ys
                    ys.add(xx)

    c = 0
    for i, v in enumerate(p, 1):
        if i == v:
            c += 1
        elif i in ss and v in ss[i]:
            c += 1
    print(c)

main()

Solution (Python):
import sys
from collections import deque
import copy


def get_read_func(fileobject):
    if fileobject == None :
        return raw_input
    else:
        return fileobject.readline

def main():
    if len(sys.argv) > 1:
        f = open(sys.argv[1])
    else:
        f = None
    read_func = get_read_func(f);
    input_raw = read_func().strip().split()
    [N, M] = [int(input_raw[0]),int(input_raw[1])]
    p_list = []
    input_raw = read_func().strip().split()
    for i in range(N):
        p_list.append(int(input_raw[i]))
    swap_list = {}
    for i in range(M):
        input_raw = read_func().strip().split()
        [x, y] =  [int(input_raw[0]),int(input_raw[1])]
        if x not in swap_list:
            swap_list[x] = [y]
        else:
            swap_list[x].append(y)
        if y not in swap_list:
            swap_list[y] = [x]
        else:
            swap_list[y].append(x)

    done_list = [False for i in range(N + 1)]
    done_list[0] = True

    adj_set_list = [set([]) for i in range(N + 1)]
    
    for i in range(1, N + 1):

        if done_list[i] == True:
            continue
        nd_list = deque([i])
        while 1:
            if len(nd_list) == 0:
                break
            nd = nd_list.popleft()
            
            adj_set_list[i].add(nd)
            adj_set_list[nd] = adj_set_list[i]
            if nd in swap_list:
                for adj in swap_list[nd]:
                    if done_list[adj] == True:
                        continue
                    done_list[adj] = True
                    nd_list.append(adj)
    count = 0
    for i in range(len(p_list)):
        if p_list[i] in adj_set_list[i + 1]:
            count += 1
    print count




if __name__ == '__main__':
    main()

Solution (Python):
class UnionFind(object):
  def __init__(self,n):
    self.table=[-1]*n
 
  def find(self,x):
    parent=self.table[x]
    if parent<0:
      return x
    else:
      root=self.find(parent)
      self.table[x]=root
      return root
 
  def union(self,a,b):
    root1=self.find(a)
    root2=self.find(b)
    if root1 != root2:
      if self.table[root1] != self.table[root2]:
        if self.table[root1] < self.table[root2]:
          self.table[root2]=root1
        else:
          self.table[root1]=root2
      else:
        self.table[root1]+=(-1)
        self.table[root2]=root1
        
N,M=map(int,input().split())
A=[int(x) for x in input().split()]
uf=UnionFind(N)
for i in range(M):
  a,b=map(int,input().split())
  uf.union(a-1,b-1)
ans=0
for i in range(N):
  if A[i]==i+1:
    ans+=1
  else:
    if uf.find(A[i]-1)==uf.find(i):
      ans+=1
print(ans)

Solution (Python):
import itertools as it
import collections as col

import sys
sys.setrecursionlimit(10000)

class UnionFind:
    def __init__(self):
        '''\
Create an empty union find data structure.'''
        self.num_weights = {}
        self.parent_pointers = {}
        self.num_to_objects = {}
        self.objects_to_num = {}
        self.__repr__ = self.__str__
    def insert_objects(self, objects):
        '''\
Insert a sequence of objects into the structure.  All must be Python hashable.'''
        for object in objects:
            self.find(object);
    def find(self, object):
        '''\
Find the root of the set that an object is in.
If the object was not known, will make it known, and it becomes its own set.
Object must be Python hashable.'''
        if not object in self.objects_to_num:
            obj_num = len(self.objects_to_num)
            self.num_weights[obj_num] = 1
            self.objects_to_num[object] = obj_num
            self.num_to_objects[obj_num] = object
            self.parent_pointers[obj_num] = obj_num
            return object
        stk = [self.objects_to_num[object]]
        par = self.parent_pointers[stk[-1]]
        while par != stk[-1]:
            stk.append(par)
            par = self.parent_pointers[par]
        for i in stk:
            self.parent_pointers[i] = par
        return self.num_to_objects[par]
    def union(self, object1, object2):
        '''\
Combine the sets that contain the two objects given.
Both objects must be Python hashable.
If either or both objects are unknown, will make them known, and combine them.'''
        o1p = self.find(object1)
        o2p = self.find(object2)
        if o1p != o2p:
            on1 = self.objects_to_num[o1p]
            on2 = self.objects_to_num[o2p]
            w1 = self.num_weights[on1]
            w2 = self.num_weights[on2]
            if w1 < w2:
                o1p, o2p, on1, on2, w1, w2 = o2p, o1p, on2, on1, w2, w1
            self.num_weights[on1] = w1+w2
            del self.num_weights[on2]
            self.parent_pointers[on2] = on1
    def __str__(self):
        '''\
Included for testing purposes only.
All information needed from the union find data structure can be attained
using find.'''
        sets = {}
        for i in xrange(len(self.objects_to_num)):
            sets[i] = []
        for i in self.objects_to_num:
            sets[self.objects_to_num[self.find(i)]].append(i)
        out = []
        for i in sets.itervalues():
            if i:
                out.append(repr(i))
        return ', '.join(out)

def main():
    n,m = [int(x) for x in input().split()]
    p = [int(x)-1 for x in input().split()]
    g = [[int(x)-1 for x in input().split()] for _ in range(m)]
    uf = UnionFind()
    uf.insert_objects(p)
    for x,y in g:
        uf.union(x,y)

    count = 0
    for x,y in enumerate(p):
        if uf.find(x) == uf.find(y):
            count +=1
    print(count)


if __name__ == '__main__':
    main()

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

par = list(range(N+1))
rank = [0]*(N+1)


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 find(x) == find(y)


ans = 0
for i in range(M):
    unite(xy[i][0], xy[i][1])

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

Solution (Python):
import queue
N,M=map(int,input().split())
p=[int(i)-1 for i in input().split()]
x=[0 for i in range(M)]
y=[0 for i in range(M)]
edge=[set() for i in range(N)]
for i in range(M):
    x[i],y[i]=map(int,input().split())
    x[i]-=1;y[i]-=1
    edge[x[i]].add(y[i])
    edge[y[i]].add(x[i])
k=0
L=[0 for i in range(N)]
q=queue.Queue()
reached=[0 for i in range(N)]
for i in  range(N):
    if reached[i]==1:
        continue
    k+=1
    q.put(i)
    reached[i]=1
    L[i]=k
    while(not(q.empty())):
        r=q.get()
        for v in edge[r]:
            if not(reached[v]):
                q.put(v)
                reached[v]=1
                L[v]=k
ans=0
for i in range(N):
    if L[i]==L[p[i]]:
        ans+=1
print(ans)

Solution (Python):
def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

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


N, M = map(int, input().split())
ps = list(map(lambda x: int(x) - 1, input().split()))

parent = [i for i in range(N)]
rank = [0] * N

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

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

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

print(ans)

Solution (Python):


class UnionFind:

    def __init__(self, n):
        self.p = {i: i for i in range(n)}
        self.r = {i: 0 for i in range(n)}

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

    def merge(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 cluster(self):
        c = {}
        for x in self.p:
            xx = self.root(x)
            if xx not in c:
                c[xx] = {x}
            else:
                c[xx].add(x)
        return c


def main():
    n, m = list(map(int, input().split()))
    pp = list(map(int, input().split()))
    uf = UnionFind(n)
    for _ in range(m):
        x, y = map(int, input().split())
        uf.merge(x - 1, y - 1)
    cc = uf.cluster()
    count = 0
    for clt in cc.values():
        p = set(pp[i] - 1 for i in clt)
        count += len(p & clt)
    print(count)


if __name__ == '__main__':
    main()

Solution (Python):

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 solve(N, M, P, xy):
    uf = UnionFind(N + 1)
    for x, y in xy:
        uf.union(x, y)
    result = 0
    for i, n in enumerate(P):
        if uf.find(i + 1) == uf.find(n):
            result += 1
    return result

N, M = [int(x) for x in input().split()]
P = [int(x) for x in input().split()]
xy = [[int(x) for x in input().split()] for i in range(M)]

print(solve(N, M, P, xy))

Solution (Python):
class UnionFind:

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

    def find(self, x):
        
        while self.table[x] >= 0:
            if self.table[self.table[x]] >= 0:
                self.table[x] = self.table[self.table[x]]
            x = self.table[x]

        return 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 self.table[s1]


n,m = map(int, input().split())
p = list(map(int, input().split()))
uf = UnionFind(2*n)
for i in range(n):
    uf.union(n+i, p[i]-1)
for i in range(m):
    x,y = map(int, input().split())
    uf.union(n+x-1, n+y-1)

cnt = 0
for i in range(n):
    if uf.find(i) == uf.find(n+i):
        cnt += 1
print(cnt)

Solution (Python):

def inpl(): return map(int, input().split())

class UnionFindTree():
    
    def __init__(self, N):
        self.parent = [-1]*(N+1)
        self.rank = [1]*(N+1)
        self.size = [1]*(N+1)
  
    def find(self, i):
        if self.parent[i] == -1:
            group = i
        else:
            group = self.find(self.parent[i]) 
            self.parent[i] = group
        return group
      
    def unite(self, x, y):
        px = self.find(x)
        py = self.find(y)
        if px != py:
            if self.rank[px] == self.rank[py]: 
                self.rank[px] += 1
            elif self.rank[px] < self.rank[py]:
                px, py = py, px
                
            self.parent[py] = px
            self.size[px] += self.size[py]
    
    def getsize(self, x):
        return self.size[self.find(x)]
    
    def groups(self, index1=True):
        return set([self.find(i) for i in range(0+index1, N+index1)])

N, M = inpl()
P = list(inpl())

UFT = UnionFindTree(N)
for m in range(M):
    x, y = inpl()
    UFT.unite(x, y)

ans = sum([UFT.find(i) == UFT.find(p) for i, p in enumerate(P, start=1)])
print(ans)

Solution (Python):
N, M = map(int, input().split())
*P, = map(int, input().split())
*p, = range(N)
def root(x):
    if x == p[x]:
        return x
    y = p[x] = root(p[x])
    return y
def unite(x, y):
    px = root(x); py = root(y)
    if px == py:
        return 0
    if px < py:
        p[py] = px
    else:
        p[px] = py
    return 1

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

pp = [set() for i in range(N)]
qq = [set() for i in range(N)]
for i in range(N):
    r = root(i)
    pp[r].add(i)
    qq[r].add(P[i]-1)

ans = 0
for i in range(N):
    ans += len(pp[i] & qq[i])
print(ans)

Solution (Python):
N,M = map(int,input().split())
ps = list(map(lambda x:int(x)-1,input().split()))
xys = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(M)]

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)
for x,y in xys:
    if uf.is_same(x,y): continue
    uf.unite(x,y)

ans = 0
for i,p in enumerate(ps):
    if i==p or uf.is_same(i,p):
        ans += 1
print(ans)

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


n, m = map(int, input().split())
uft = UnionFind(n)
ppp = list(map(int, input().split()))
rev = {x: i for i, x in enumerate(ppp)}

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

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

print(ans)

Solution (Python):


import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq





def solve(f):
    n, m = f.read_int_list()
    p = [i-1 for i in f.read_int_list()]
    uf = UnionFind(n)
    for _ in xrange(m):
        x, y = f.read_int_list()
        uf.unite(x-1, y-1)

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

    return ans


class UnionFind(object):
    def __init__(self, number_of_nodes):
        
        self.par = array.array("L", range(number_of_nodes))
        self.rank = array.array("L", (0 for _ in range(number_of_nodes)))

    def root(self, node):
        if self.par[node] == node:
            return node
        else:
            r = self.root(self.par[node])
            self.par[node] = r
            return r

    def in_the_same_set(self, node1, node2):
        return self.root(node1) == self.root(node2)

    def unite(self, node1, node2):
        x = self.root(node1)
        y = self.root(node2)
        if x == y:
            pass
        elif 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


class Reader(object):
    def __init__(self, filename=None):
        self.file = open(filename) if filename is not None else None
        self.case = 1

    def __readline(self):
        return self.file.next().strip() if self.file else raw_input()

    def next_case(self):
        self.file.next()
        self.case += 1

    def read_int(self): return int(self.__readline())
    def read_float(self): return float(self.__readline())
    def read_long(self): return long(self.__readline())
    def read_decimal(self): return decimal.Decimal(self.__readline())
    def read_str(self): return self.__readline()

    def read_int_list(self): return map(int, self.__readline().split())
    def read_float_list(self): return map(float, self.__readline().split())
    def read_long_list(self): return map(long, self.__readline().split())
    def read_decimal_list(self): return map(decimal.Decimal, self.__readline().split())
    def read_str_list(self): return self.__readline().split()

if __name__ == '__main__':
    filename = sys.argv[1] if len(sys.argv) > 1 else None
    f = Reader(filename)
    if f.file:
        while True:
            print "Case 
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)