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:
import sys
IS = lambda: sys.stdin.readline().rstrip()
II = lambda: int(IS())
MII = lambda: list(map(int, IS().split()))
_DEC = lambda x: x-1
MIIZ = lambda: list(map(_DEC, MII()))

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

def main():
    n, m = MII()
    pp = MIIZ()
    uf = UnionFind(n)
    for i in range(m):
        x, y = MIIZ()
        uf.union(x, y)
    cnt = 0
    for i, p in enumerate(pp):
        if uf.find(i) == uf.find(p): cnt += 1
    print(cnt)

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

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

N,M=map(int,input().split())
plist=list(map(int,input().split()))
#print(plist)

par_list=list(range(N+1))
for i in range(M):
  x,y=map(int,input().split())
  merge(x,y)
  #print(x,y,par_list)
for i in range(1,N+1):
  par_list[i]=get_par(i)
#print(par_list)
  
answer=0
for i in range(N):
  if get_par(i+1)==get_par(plist[i]):
    answer+=1
    
print(answer)

Submission status: Accepted

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

def get_par(x):
  if x == par_list[x]:
    return x
  else:
    par_list[x] = get_par(par_list[x])
    return par_list[x]

def merge(x,y):
  par_x = get_par(x)
  par_y = get_par(y)
  if par_x != par_y:
    par_list[par_y] = par_x

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

N,M=map(int,input().split())
plist=list(map(int,input().split()))
#print(plist)

par_list=list(range(N+1))
for i in range(M):
  x,y=map(int,input().split())
  merge(x,y)
#print(par_list)

index_dic={}
comp_list=[]
for i in range(1,N+1):
  par=get_par(par_list[i])
  comp_list.append(par)
  if par in index_dic:
    index_dic[par].append(i)
  else:
    index_dic[par]=[i]
#print(comp_list)
#print(index_dic)

answer=0
for par,vlist in index_dic.items():
  v2set=set()
  for v in vlist:
    v2set.add(plist[v-1])
      
  #print(vlist)
  #print(v2set)
  for v in vlist:
    if v in v2set:
      answer+=1
      
print(answer)

Submission status: Accepted

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

class UnionFind:
    __slots__ = ["data"]
    
    def __init__(self, n=0):
        self.data = [-1]*(n+1)
    
    def root(self, x):
        if self.data[x] < 0:
            return x
        self.data[x] = self.root(self.data[x])
        return self.data[x]
    
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x != y:
            if self.data[x] < self.data[y]:
                self.data[x] += self.data[y]
                self.data[y] = x
            else:
                self.data[y] += self.data[x]
                self.data[x] = y
    
    def same(self, x, y):
        return self.root(x) == self.root(y)
    
    def size(self, x):
        return -self.data[self.root(x)]


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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    parent = list(range(n+1))
    rank = [0]*(n+1)
    cnt = 0
    
    def root(x):
        if parent[x] == x:
            return x
        parent[x] = root(parent[x])
        return parent[x]
    
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x != y:
            if rank[x] > rank[y]:
                parent[y] = x
            elif rank[x] < rank[y]:
                parent[x] = y
            else:
                parent[y] = x
                rank[x] += 1

    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i, pi in enumerate(p, 1):
        if root(i) == root(pi):
            cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

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

def main():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    parent = list(range(n+1))
    rank = [0]*(n+1)
    cnt = 0
    
    def root(x):
        if parent[x] == x:
            return x
        parent[x] = root(parent[x])
        return parent[x]
    
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x != y:
            if rank[x] < rank[y]:
                parent[x] = y
            elif rank[x] > rank[y]:
                parent[y] = x
            else:
                parent[y] = x
                rank[x] += 1

    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i, pi in enumerate(p, 1):
        if root(i) == root(pi):
            cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.buffer.readline
def main():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    parent = list(range(n+1))
    rank = [0]*(n+1)
    cnt = 0
    
    def root(x):
        if parent[x] == x:
            return x
        parent[x] = root(parent[x])
        return parent[x]
    
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x != y:
            if rank[x] < rank[y]:
                parent[x] = y
            elif rank[x] > rank[y]:
                parent[y] = x
            else:
                parent[y] = x
                rank[x] += 1

    for _ in range(m):
        x, y = map(int, input().split())
        x = root(x)
        y = root(y)
        if x != y:
            parent[y] = x
    for i, pi in enumerate(p, 1):
        if root(i) == root(pi):
            cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    parent = list(range(n+1))
    rank = [0]*(n+1)
    cnt = 0
    
    def root(x):
        if parent[x] == x:
            return x
        parent[x] = root(parent[x])
        return parent[x]
    
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x != y:
            if rank[x] < rank[y]:
                parent[x] = y
            elif rank[x] > rank[y]:
                parent[y] = x
            else:
                parent[y] = x
                rank[x] += 1

    for _ in range(m):
        x, y = map(int, input().split())
        x = root(x)
        y = root(y)
        if x != y:
            parent[y] = x
    for i, pi in enumerate(p, 1):
        if root(i) == root(pi):
            cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    parent = list(range(n+1))
    rank = [0]*(n+1)
    cnt = 0
    
    def root(x):
        if parent[x] == x:
            return x
        parent[x] = root(parent[x])
        return parent[x]
    
    def unite(x, y):
        x = root(x)
        y = root(y)
        if x != y:
            if rank[x] < rank[y]:
                parent[x] = y
            elif rank[x] > rank[y]:
                parent[y] = x
            else:
                parent[y] = x
                rank[x] += 1

    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i, pi in enumerate(p, 1):
        if root(i) == root(pi):
            cnt += 1
    print(cnt)

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
def main():
    cnt = 0
    for _ in range(m):
        x, y = map(int, input().split())
        unite(x, y)
    for i, pi in enumerate(p, 1):
        if root(i) == root(pi):
            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):
    x = root(x)
    y = root(y)
    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
        elif rank[x] > rank[y]:
            parent[y] = x
        else:
            parent[y] = x
            rank[x] += 1

if __name__ == "__main__":
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    parent = list(range(n+1))
    rank = [0]*(n+1)
    main()

Submission status: Accepted

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

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

def unite(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
        elif rank[x] > rank[y]:
            parent[y] = x
        else:
            parent[y] = x
            rank[x] += 1

if __name__ == "__main__":
    main()

Submission status: Accepted

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

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

def unite(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
        elif rank[x] > rank[y]:
            parent[y] = x
        else:
            parent[y] = x
            rank[x] += 1

if __name__ == "__main__":
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    parent = list(range(n+1))
    rank = [0]*(n+1)
    main()

Submission status: Accepted

Solution code:
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]):
            cnt += 1
    print(cnt)
        
def root(x):
    if parent[x] == x:
        return x
    parent[x] = root(parent[x])
    return parent[x]

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

def unite(x, y):
    x = root(x)
    y = root(y)
    if x != y:
        if rank[x] < rank[y]:
            parent[x] = y
        elif rank[x] > rank[y]:
            parent[y] = x
        else:
            parent[y] = x
            rank[x] += 1

if __name__ == "__main__":
    n, m = map(int, input().split())
    p = [0] + list(map(int, input().split()))
    parent = list(range(n+1))
    rank = [0]*(n+1)
    main()

Submission status: Accepted

Solution code:
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]):
            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):
    rx = root(x)
    ry = root(y)
    return rx == ry

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 = [0] + list(map(int, input().split()))
    par = list(range(n+1))
    main()

Submission status: Accepted

Solution code:
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]):
            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)
    if x != root(y):
        par[x] = y

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

Submission status: Accepted

Solution code:
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]):
            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 = [0] + list(map(int, input().split()))
    par = list(range(n+1))
    main()

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
class UnionFind():
    # 作りたい要素数nで初期化
    # 使用するインスタンス変数の初期化
    def __init__(self, n):
        self.n = n
        # root[x]<0ならそのノードが根かつその値が木の要素数
        # rootノードでその木の要素数を記録する
        self.root = [-1]*(n+1)
        # 木をくっつける時にアンバランスにならないように調整する
        self.rnk = [0]*(n+1)

    # ノードxのrootノードを見つける
    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):
        # 入力ノードのrootノードを見つける
        x = self.Find_Root(x)
        y = self.Find_Root(y)
        # すでに同じ木に属していた場合
        if(x == y):
            return 
        # 違う木に属していた場合rnkを見てくっつける方を決める
        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
            # rnkが同じ（深さに差がない場合）は1増やす
            if(self.rnk[x] == self.rnk[y]):
                self.rnk[y] += 1
    # xとyが同じグループに属するか判断
    def isSameGroup(self, x, y):
        return self.Find_Root(x) == self.Find_Root(y)

    # ノードxが属する木のサイズを返す
    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()

Submission status: Accepted

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

    # 要素xが属するグループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    # 要素xが属するグループと要素yが属するグループとを併合する
    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

    # 要素xが属するグループのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]

    # 要素x, yが同じグループに属するかどうかを返す
    def same(self, x, y):
        return self.find(x) == self.find(y)

    # 要素xが属するグループに属する要素をリストで返す
    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()}

    # print()での表示用 ルート要素: [そのグループに含まれる要素のリスト]を文字列で返す
    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) # x-1の木とy-1の木を併合する

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

print(cnt)

Submission status: Accepted

Solution code:
# 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,子なら親の頂点
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)

Submission status: Accepted

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

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

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

Submission status: Accepted

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

Submission status: Accepted

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