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:
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 = set()
    for i in part:
        part2.add(p[i-1])
    for i in part:
        if i in part2:
            ans += 1
print(ans)

Submission status: Accepted

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

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

def union(x,y,tree):
    a=root(x,tree)
    b=root(y,tree)
    if a==b:
        return
    else:
        tree[a]=b

ans=n


for i in range(m):
    x,y=map(int,input().split())
    union(x,y,tree)

for i in range(n):
    if  root(p[i],tree)!=root(i+1,tree):
        ans-=1
print(ans)

Submission status: Accepted

Solution code:
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
    # G = [i for i in range(N + 1)]

    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()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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

# union-find
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# coding: utf-8
# Your code here!

class UnionFind():
    #負の値はルートで集合の個数
    #正の値は次の要素を返す
    def __init__(self,size):
        self.table = [-1 for _  in range(size)]

    #集合の代表を求める
    def find(self,x):
        while self.table[x] >= 0:
            #根に来た時,self.table[根のindex]は負の値なのでx = 根のindexで値が返される。
            x = self.table[x]
        return x

    #併合
    def union(self,x,y):
        s1 = self.find(x)#根のindex,table[s1]がグラフの高さ
        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:
                #グラフの長さが同じ場合,どちらを根にしても変わらない
                #その際,グラフが1長くなることを考慮する
                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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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()
            #done_list[nd] = True
            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()

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:


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()

Submission status: Accepted

Solution code:
# http://www.geocities.jp/m_hiroi/light/pyalgo61.html
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))

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
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]: # rank is same
                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)

Submission status: Accepted

Solution code:
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)

Submission status: Accepted

Solution code:
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)

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


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)

Submission status: Accepted

Solution code:
#!/usr/bin/python
# -*- coding: utf-8 -*-
import sys,collections,itertools,re,math,fractions,decimal,random,array,bisect,heapq

# decimal.getcontext().prec = 50
# sys.setrecursionlimit(10000)
# MOD = 10**9 + 7

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):
        # Don't use self.par directly! (call self.root)
        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 #%d\n"%f.case, solve(f)
            try:
                f.next_case()
            except StopIteration:
                break
    else:
        print solve(f)

Submission status: Runtime Error

Solution code:
def read_values(): return map(int, input().split())
def read_index(): return map(lambda x: int(x) - 1, input().split())
def read_list(): return list(read_values())
def read_lists(N): return [read_list() for n in range(N)]


class UF:
    def __init__(self, N):
        self.state = [-1] * N
        self.rank = [0] * N
        self.num_group = N
    
    def get_parent(self, a):
        p = self.state[a]
        if p < 0:
            return a
        
        q = self.get_parent(p)
        self.state[a] = q
        return q

    def make_pair(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa == pb:
            return

        if self.rank[pa] > self.rank[pb]:
            pa, pb = pb, pa
            a, b = b, a
        elif self.rank[pa] == self.rank[pb]:
            self.rank[pb] += 1

        self.state[pb] += self.state[pa]
        self.state[pa] = pb
        self.state[a] = pb
        self.num_group -= 1
    
    def is_pair(self, a, b):
        return self.get_parent(a) == self.get_parent(b)

    def get_size(self, a):
        return -self.state[self.get_parent(a)]

N, M = read_values()
A = read_list()
uf = UF(N)
for _ in range(M):
    i, j = read_index()
    uf.make_pair(A[i] - 1, A[j] - 1)

res = 0
for i, a in enumerate(A):
    if uf.is_pair(i, A[i] - 1)

print(res)