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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
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): # xが属するグループのサイズを返す
        return -self.root[self.Find_Root(x)]
    def Members(self, x): # 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)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

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

#xの根を求める
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
#xとyの属する集合の併合
def unite(x,y):
    x = find(x)
    y = find(y)

    if x == y:
        return False
    else:
        #sizeの大きいほうがx
        if par[x] > par[y]:
            x,y = y,x
        par[x] += par[y]
        par[y] = x
        return True

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

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

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

###具体例###
for _ in range(m):
    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)

Submission status: Accepted

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

Submission status: Accepted

Solution code:
#097_D
n, m = map(int, input().split())
p = [int(x)-1 for x in input().split()]

#Union-Find
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)

Submission status: Accepted

Solution code:
# union-find
# こういう問題のときにUnion-Findなのか幅優先探索なのか深さ優先探索なのか迷う。
# ちなみに解説PDFはUnion-Findを挙げている。

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 = [0]*n
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] #1-idx -> 0-idx

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

ans = 0
for i in range(n):
    num = init_nums[i]
    # i+1 が init_numの中でi+1と同じグループだったら
    if is_same(i, num - 1):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# union-find

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 = [0]*n
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] #1-idx -> 0-idx

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

# print(par)
# print(len(set(par)))

ans = 0
for i in range(n):
    num = init_nums[i]
    # i+1 が init_numの中でi+1と同じグループだったら
    if is_same(i, num - 1):
        ans += 1

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

print(ans)

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

count = 0
for i, p_ in enumerate(p):
    count += 1 if is_same(i, p_) else 0
print(count)

Submission status: Accepted

Solution code:
import sys


class UnionFind():
    def __init__(self, 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


N, M = map(int, input().split())
P = list(map(int, input().split()))
uf = UnionFind(N)
for IN in sys.stdin.readlines():
    x, y = map(int, IN.split())
    x -= 1; y -= 1
    uf.union(x, y)

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

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.parents = [i for i in range(n)]

    def find(self, x):
        if self.parents[x] == x:
            return x
        ret = self.parents[x] = self.find(self.parents[x])
        return ret

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

    def union(self, x, y):
        root_x = self.find(x)
        root_y = self.find(y)
        if root_x == root_y:
            return False
        self.parents[root_x] = root_y
        return True


n, m = [int(i) for i in input().split()]
pp = [int(i)-1 for i in input().split()]
uf = UnionFind(n)
for _ in range(m):
    x, y = [int(i) for i in input().split()]
    uf.union(x-1, y-1)

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

print(ans)

Submission status: Accepted

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

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

    def isSameGroup(self,x,y):
        return self.Find_Root(x)==self.Find_Root(y)

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

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

    def address(self):
        return[i for i,j in enumerate(self.root) if j<0]

    def group_members(self):
        return {i:self.members(i) for i in self.address()}


n,m=map(int,input().split())
P=list(map(int,input().split()))
XY=[list(map(lambda x: int(x)-1,input().split())) for _ in range(m)]

UnionFind=UnionFind(n)
for x,y in XY:
    UnionFind.Unite(x,y)

cnt=0
for num,p in enumerate(P):
    if UnionFind.isSameGroup(num,p-1):
        cnt +=1

print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
P=list(map(int,input().split()))
par=list(range(n+1))

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

for i in range(m):
    x,y=map(int,input().split())
    bx,by=find(x),find(y)
    par[y]=bx
    par[by]=bx

ans=0

for i in range(1,n+1):
    if find(i)==find(P[i-1]):
        ans+=1
print(ans)

Submission status: Accepted

Solution code:

import sys
sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline

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

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

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

    def union(self, x, y):
        x = self.root(x)
        y = self.root(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.root(x)]

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

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

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

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

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

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

uf = UnionFind(n)
ab = [tuple(map(int,input().split())) for i in range(m)]
for a,b in ab:
    a,b = a-1,b-1
    if uf.is_same(a,b): continue
    uf.union(a,b)

ans = 0

loop = [set() for i in range(n)]
for i in range(n):
    r = uf.root(i)
    loop[r].add(i)

for i in range(n):
    for j in loop[i]:
        if p[j]-1 in loop[i]: ans += 1

print(ans)

Submission status: Accepted

Solution code:
# Author: cr4zjh0bp
# Created: Sat Mar 14 09:09:09 UTC 2020
import sys
 
stdin = sys.stdin
inf = 1 << 60
mod = 1000000007
 
ni = lambda: int(ns())
nin = lambda y: [ni() for _ in range(y)]
na = lambda: list(map(int, stdin.readline().split()))
nan = lambda y: [na() for _ in range(y)]
nf = lambda: float(ns())
nfn = lambda y: [nf() for _ in range(y)]
nfa = lambda: list(map(float, stdin.readline().split()))
nfan = lambda y: [nfa() for _ in range(y)]
ns = lambda: stdin.readline().rstrip()
nsn = lambda y: [ns() for _ in range(y)]
ncl = lambda y: [list(ns()) for _ in range(y)]
nas = lambda: stdin.readline().split()

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

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

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

n, m = na()
p = na()
uf = UnionFind(n)
for i in range(m):
    x, y = na()
    x -= 1
    y -= 1
    uf.unite(x, y)

d = dict()
for i in range(n):
    d[p[i] - 1] = i

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

print(ans)

Submission status: Accepted

Solution code:
def get_root(s):
    if s != root[s]:
        root[s] = get_root(root[s])
        return root[s]
    return s

def unite(s, t):
    root_s = get_root(s)
    root_t = get_root(t)
    if not root_s == root_t:
        if rank[s] == rank[t]:
            root[root_t] = root_s
            rank[root_s] += 1
        elif rank[s] > rank[t]:
            root[root_t] = root_s
        else:
            root[root_s] = root_t

def same(s, t):
    if get_root(s) == get_root(t):
        return True
    else:
        return False

n, m = map(int, input().split())
p = list(map(int, input().split()))
root = [i for i in range(n)]
rank = [1 for _ in range(n)]
for _ in range(m):
    x, y = map(int, input().split())
    unite(x - 1, y - 1)
ans = 0
for i in range(n):
    if get_root(i) == get_root(p[i] - 1):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
n,m=map(int,input().split())
p=list(map(int,input().split()))
def root(x):
	if x!=parent[x]:
		x=root(parent[x])
	return x
def same (x,y):
	return root(x)==root(y)
def unite(x,y):
	rx=root(x)
	ry=root(y)
	if rank[rx]<rank[ry]:
		parent[rx]=ry
	else:
		parent[ry]=rx
		if rank[rx]==rank[ry]:
			rank[rx]+=1
parent=list(range(n))
rank=[0]*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(p[i]-1,i):
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline

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 members(self,x):#xと同じグループのメンバーを列挙
        root=self.find(x)
        return [i for i in range(self.n) if self.find(i)==root]
    
    def size(self,x):#xが属するグループのメンバーの数
        return -self.parents[self.find(x)]
    
    def roots(self):#ufの根を列挙
        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):#print()での表示用
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

def main():
    n,m = map(int,input().split())
    p = [int(i)-1 for i in input().split()]
    dic = {i:idx for idx,i in enumerate(p)}   

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

Submission status: Accepted

Solution code:
# Union Find 木
from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[j] += parent[i]
    parent[i] = j


setrecursionlimit(10 ** 5)


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

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

result = 0
for i in range(N):
    if find(parent, i) == find(parent, p[i] - 1):
        result += 1
print(result)

Submission status: Accepted

Solution code:
# ABC097D - Equals (ARC097D)
class UnionFind:
    __slots__ = ["_data_size", "_first_index", "_parents"]

    def __init__(self, data_size: int, is_zero_indexed: bool = True) -> None:
        self._data_size = data_size
        self._first_index = 0 if is_zero_indexed else 1
        self._parents = [-1] * (data_size + self._first_index)

    def find(self, x: int) -> int:
        """Find the group (root) of vertex x"""
        if self._parents[x] < 0:
            return x
        self._parents[x] = self.find(self._parents[x])
        return self._parents[x]

    def is_same(self, x: int, y: int) -> bool:
        """Return whether two vertices x and y are in the same group or not."""
        return self.find(x) == self.find(y)

    def unite(self, x: int, y: int) -> None:
        """Unite two groups of vertices x and y."""
        x, y = self.find(x), 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 main():
    N, _, *PXY = map(int, open(0).read().split())
    P, XY = PXY[:N], PXY[N:]
    uf = UnionFind(N, is_zero_indexed=False)
    for x, y in zip(*[iter(XY)] * 2):
        uf.unite(x, y)
    ans = sum(uf.is_same(i, p) for i, p in enumerate(P, 1))
    print(ans)


if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys

input = sys.stdin.readline


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


def read_list():
    return list(read_values())


def func(N, mod):
    F = [1]
    for i in range(1, N + 1):
        F.append(F[-1] * i % mod)
    return F


INV = {}


def inv(a, mod):
    if a in INV:
        return INV[a]
    r = pow(a, mod - 2, mod)
    INV[a] = r
    return r


def C(F, a, b, mod):
    return F[a] * inv(F[b], mod) * inv(F[a - b], mod) % mod


class UF:
    def __init__(self, N):
        self.parent = [i for i in range(N)]

    def get_parent(self, a):
        p = self.parent[a]
        if a == p:
            return a

        q = self.get_parent(p)
        self.parent[a] = q
        return q

    def make_pare(self, a, b):
        pa = self.get_parent(a)
        pb = self.get_parent(b)
        if pa != pb:
            self.parent[pa] = pb
            self.parent[a] = pb

    def is_pare(self, a, b):
        return self.get_parent(a) == self.get_parent(b)


def main():
    N, M = read_values()
    P = read_list()
    F = [0] * N

    W = [tuple(read_values()) for _ in range(M)]
    U = UF(N)
    for a, b in W:
        a -= 1
        b -= 1
        U.make_pare(a, b)

    res = 0
    for p in P:
        p -= 1
        if U.is_pare(p, P[p] - 1):
            res += 1
    print(res)


if __name__ == "__main__":
    main()