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

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
N, M = [int(x) for x in input().strip().split()]
p = [int(x) for x in input().strip().split()]
par = [i for i in range(N+1)]
rank = [0] * (N+1)

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

def isSame(x, y):
    return find(x) == find(y)

def union(x, y):
    x = find(x)
    y = find(y)
    if x == y:
        return 

    if rank[x] >= rank[y]:
        par[y] = x
        if rank[x] == rank[y]:
            rank[x] += 1
    else:
        par[x] = y

for m in range(M):
    x, y = [int(x) for x in input().strip().split()]
    union(x, y)

ans = 0
for i in range(1, N+1):
    if isSame(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 r'\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

n,m=map(int,input().split())
u=UnionFind(n)
ans=0
p=list(map(lambda x:int(x)-1,input().split()))
for i in range(m):
  a,b=map(lambda x:x-1,map(int,input().split()))
  u.union(a,b)
for i in range(n):
  if u.same(i,p[i]):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict,deque
from heapq import heappush, heappop
from itertools import permutations
import sys
import math
import bisect
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007
"""
#N,K,Mが入力
    n,k,m=LI() 
    #N
    #x1 y1
    #.  .
    #xn ynが入力
    N=I()
    p=LIR(N)
    print(n,k,m,p)
"""
############################## ユニオン木(union tree) ###################################
#uf=UnionFind(n)と使う
# print(uf.roots())
# print(uf.all_group_members())
class UnionFind:
    def __init__(self, n):
        self.n=n
        self.par = [-1 for i in range(self.n+1)]
        self.rank = [0 for i in range(self.n+1)]#素集合でないとrankは意味がなさそう,素集合であればrank kには少なくとも2^k要素がある。
    
    # 検索
    def find(self, x):
        # if self.par[x] == x:
        if self.par[x] <0:
            return x
        else:
            self.par[x] = self.find(self.par[x])
            return self.par[x]

    # 併合
    def union(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
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
        
    # 同じ集合に属するか判定
    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+1) if self.find(i) == root]

    #すべての根の要素をリストで返す
    def roots(self):
        return [i for i, x in enumerate(self.par) if x<0]

    #グループの数を返す
    def group_count(self):
        return len(self.roots())

    #{ルート要素: [そのグループに含まれる要素のリスト], ...}の辞書を返す
    def all_group_members(self):
        return {int(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 resolve():
    n,m=LI()
    p=LI()
    x=LIR(m)

    uf=UnionFind(n)
    for i in range(m):
        uf.union(x[i][0],x[i][1])
    # print(uf.all_group_members())

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

import sys
from io import StringIO
import unittest

class TestClass(unittest.TestCase):
    def assertIO(self, input, output):
        stdout, stdin = sys.stdout, sys.stdin
        sys.stdout, sys.stdin = StringIO(), StringIO(input)
        resolve()
        sys.stdout.seek(0)
        out = sys.stdout.read()[:-1]
        sys.stdout, sys.stdin = stdout, stdin
        self.assertEqual(out, output)
    def test_入力例_1(self):
        input = """5 2
5 3 1 4 2
1 3
5 4"""
        output = """2"""
        self.assertIO(input, output)
    def test_入力例_2(self):
        input = """3 2
3 2 1
1 2
2 3"""
        output = """3"""
        self.assertIO(input, output)
    def test_入力例_3(self):
        input = """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"""
        output = """8"""
        self.assertIO(input, output)
    def test_入力例_4(self):
        input = """5 1
1 2 3 4 5
1 5"""
        output = """5"""
        self.assertIO(input, output)

if __name__ == "__main__":
    # unittest.main()
    resolve()

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self,N):
        self.parent = [i for i in range(N)]
        self.rank = [0] * N
        self.count = 0
    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
        self.count += 1

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

"""
ペアの整数をたどって目的のindexまでたどり着ければよい。
全ての数字についてやるとTLE待ったなしなので、UnionFindで同じ集合に含まれていればたどり着けるよね、という感じ
"""

uf = UnionFind(N)
for _ in range(M):
    x,y = map(int, input().split())
    uf.unite(x-1, y-1)

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

print(ans)

Submission status: Accepted

Solution code:
class UnionFind(object):
    def __init__(self, size):
        self.parent = [i for i in range(size)]
        self.size = [1]*size

    def __str__(self):
        from collections import defaultdict
        d = defaultdict(set)
        for i in range(len(self.parent)):
            d[self.find(i)].add(i)
        return str(dict(d))    

    def find(self, x):
        if self.parent[x] == x:
            return x
        self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def unite(self, x, y):
        x, y = self.find(x), self.find(y)
        if x == y:
            return
        if self.size[x] < self.size[y]:
            self.size[y] += self.size[x]
            self.parent[x] = y
        else:
            self.size[x] += self.size[y]
            self.parent[y] = x
    
    def same(self, x, y):
        return self.find(x) == self.find(y)
    
    def sizeofset(self, x):
        return self.size[self.find(x)]

if __name__ == "__main__":
    N,M = map(int,input().split())
    uf = UnionFind(N)
    p = list(map(lambda x:int(x)-1,input().split()))
    for i in range(M):
        x,y = map(lambda x:int(x)-1,input().split())
        uf.unite(x, y)
    ans = 0
    for i in range(N):
        if uf.same(p[i], i):
            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()))
xy=[]
for i in range(m):
    tmp = list(map(int,input().split()))
    xy.append(tmp)

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)

uf = UnionFind(n)

for tmp in xy:
    uf.union(tmp[0]-1,tmp[1]-1)

ans=0
for i in range(n):
    if uf.same(i,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()))
xy=[]
for i in range(m):
    tmp = list(map(int,input().split()))
    xy.append(tmp)

link = [[] for _ in range(n)]
for tmp in xy:
    link[tmp[0]-1].append(tmp[1]-1)
    link[tmp[1]-1].append(tmp[0]-1)

from collections import deque
Q = deque()

from collections import defaultdict
visited = defaultdict(int)
ans=0
for i in range(n):
    if visited[i] != 0:
        continue
    ans_1=[]
    ans_2=[]

    Q.append(i)
    ans_1.append(i+1)
    ans_2.append(p[i])
    visited[i] = 1

    while Q:
        now=Q.popleft()
        for nxt in link[now]:
            if visited[nxt] != 0:
                continue
            Q.append(nxt)
            ans_1.append(nxt+1)
            ans_2.append(p[nxt])
            visited[nxt]=1
    ans+=len(set(ans_1) & set(ans_2))
print(ans)

Submission status: Accepted

Solution code:
import os
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(10 ** 9)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7


# MOD = 998244353

class UnionFind:
    def __init__(self, size=None, nodes=None):
        """
        size か nodes どっちか指定。
        nodes は set、size は list を使う。
        :param int size:
        :param collections.Iterable nodes:
        """
        assert size is not None or nodes is not None
        if size is not None:
            self._parents = [i for i in range(size)]
            self._ranks = [0 for _ in range(size)]
            self._sizes = [1 for _ in range(size)]
        else:
            self._parents = {k: k for k in nodes}
            self._ranks = {k: 0 for k in nodes}
            self._sizes = {k: 1 for k in nodes}

    def unite(self, x, y):
        """
        x が属する木と y が属する木を併合
        :param x:
        :param y:
        """
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return

        # rank が小さい方が下
        if self._ranks[x] > self._ranks[y]:
            # x が root
            self._parents[y] = x
            self._sizes[x] += self._sizes[y]
        else:
            # y が root
            self._parents[x] = y
            self._sizes[y] += self._sizes[x]
            if self._ranks[x] == self._ranks[y]:
                self._ranks[y] += 1

    def root(self, x):
        """
        x が属する木の root
        :param x:
        """
        if self._parents[x] == x:
            return x
        self._parents[x] = self.root(self._parents[x])
        return self._parents[x]

    def size(self, x):
        """
        x が属する木のノード数
        :param x:
        """
        return self._sizes[self.root(x)]


N, M = list(map(int, sys.stdin.buffer.readline().split()))
P = list(map(int, sys.stdin.buffer.readline().split()))
XY = [list(map(int, sys.stdin.buffer.readline().split())) for _ in range(M)]

uf = UnionFind(size=N + 1)
for x, y in XY:
    uf.unite(x, y)

ans = 0
for i, p in enumerate(P, start=1):
    ans += uf.root(i) == uf.root(p)
print(ans)

Submission status: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())
P = list(map(int, input().split()))
graph = [[] for _ in range(n)]
cands = set()
for _ in range(m):
    x, y = map(int, input().split())
    graph[x - 1].append(y - 1)
    graph[y - 1].append(x - 1)
    cands.add(x - 1)

group = [-1] * n
def dfs(start, size, num):
    q = deque(maxlen=size)
    q.append(start)
    used = {start}
    group[start] = num
    while q:
        node = q.popleft()
        for to in graph[node]:
            if to in used:
                continue
            q.append(to)
            used.add(to)
            group[to] = num

count = 0
for node in cands:
    if group[node] == -1:
        dfs(node, n, count)
        count += 1

print(sum(i == P[i] - 1 or group[P[i] - 1] == group[i] != -1 for i in range(n)))

Submission status: Accepted

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

    def find(self, x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.root[x]
            
    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return 0
        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 isSame(self, x, y):
        return self.find(x) == self.find(y) or x==y
        
def solve():
    n, m = map(int, input().split())
    p = list(map(int, input().split()))
    ids = [0] * (n+1)
    for i in range(n):
        ids[p[i]] = i+1
    uf=UnionFind(n)
    for _ in range(m):
        x, y = map(int, input().split())
        uf.unite(x,y)

    print(sum(uf.isSame(i,ids[i])for i in range(1,n+1)))
    
if __name__=="__main__":
    solve()

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)
ans = 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])
    ans += (s[i] == s[j])
print(ans)

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


class UnionFind:
    def __init__(self, x):
        self.p = [e for e in range(x)]
        self.rank = [0] * x

    def same(self, u, v):
        return self.find_set(u) == self.find_set(v)

    def unite(self, u, v):
        self.link(self.find_set(u), self.find_set(v))

    def find_set(self, u):
        if u != self.p[u]:
            self.p[u] = self.find_set(self.p[u])

        return self.p[u]

    def link(self, u, v):
        if self.rank[u] > self.rank[v]:
            self.p[v] = u
        else:
            self.p[u] = v
            if self.rank[u] == self.rank[v]:
                self.rank[v] += 1


uf = UnionFind(n)

for x, y in xy:
    x -= 1
    y -= 1
    uf.unite(x, y)

cnt = 0
for e in p:
    e -= 1
    if uf.find_set(e) == uf.find_set(p[e] - 1):
        cnt += 1

print(cnt)

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)]
      
N,M = map(int,input().split())
List=list(map(int,input().split()))

List2=[list(map(int,input().split())) for i in range(M)]
uf = UnionFind(N+1)

for i in range(M):
  a = List2[i][0]
  b = List2[i][1]  
  uf.Unite(a, b)
  
cnt = 0
for i,w in enumerate(List):
  if uf.Find_Root(i+1) == uf.Find_Root(w):
    cnt += 1
  
print(cnt)

Submission status: Accepted

Solution code:
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 = map(int,input().split())
List=list(map(int,input().split()))

List2=[list(map(int,input().split())) for i in range(M)]
uf = UnionFindTree(N+1)

for i in range(M):
  a = List2[i][0]
  b = List2[i][1]  
  uf.unite(a, b)
  
cnt = 0
for i,w in enumerate(List):
  if uf.find(i+1) == uf.find(w):
    cnt += 1
  
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.par = [-1 for _ in range(n)]

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

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

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

        if self.par[x]>self.par[y]:
            x,y = y,x

        self.par[x] += self.par[y]
        self.par[y] = x

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

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

u = UnionFind(n+1)
for _ in range(m):
  x,y = map(int, input().split())
  u.unite(x,y)

res = 0
for i in range(1,n+1):
  if u.same(i,pl[i-1]):
    res += 1
print(res)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
P=[0]+list(map(int, input().split()))
E=[[] for _ in range(N+1)]
for _ in range(M):
    x,y=map(int, input().split())
    E[x].append(y)
    E[y].append(x)

ans=[0]*(N+1)
parent=[0]*(N+1)

for root in range(1,N+1):
    if parent[root]: continue
    parent[root]=root
    stack=[root]
    nodes=set()
    values=set()
    while stack:
        node=stack.pop()
        nodes.add(node)
        values.add(P[node])
        for to in E[node]:
            if parent[to]: continue
            parent[to]=node
            stack.append(to)
    for i in nodes&values:
        ans[i]=1

print(sum(ans))

Submission status: Accepted

Solution code:
# input = sys.stdin.readline
from bisect import *
from collections import *
from heapq import *
# import functools
# import itertools
# import math

N,M=map(int,input().split())
p=list(map(int,input().split()))
xy=[list(map(int,input().split())) for m in range(M)]

data=[[] for i in range(N+1)]
ittenai=set()

for x,y in xy:
    data[x].append(y)
    data[y].append(x)
    ittenai.add(x)
    ittenai.add(y)
#print(ittenai)
count=len([i for i in range(N) if not i+1 in ittenai and p[i]==i+1])
while ittenai:
    stack=[ittenai.pop()]
    idxlst=set([stack[0]])
    while stack:
        idx=stack.pop()
        for i in data[idx]:

            if not i in idxlst:
                idxlst.add(i)
                stack.append(i)
                ittenai.remove(i)
    idxlst=list(idxlst)
    numlst=set([p[i-1] for i in idxlst])
    #print(idxlst,numlst)
    for i in idxlst:
        count+=i in numlst


print(count)

Submission status: Accepted

Solution code:
#### ARC097D - Equals
#https://atcoder.jp/contests/arc097/tasks/arc097_b
# 参考URL
# https://note.nkmk.me/python-union-find/
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 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]
 
 
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.union(x-1, y-1)
 
ans = 0

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

Submission status: Accepted

Solution code:
def root(v):
    if v == par[v]:
        return v
    par[v] = root(par[v])
    return par[v]

def unite(u, v):
    u = root(u)
    v = root(v)
    if u == v:
        return
    if rank[u] < rank[v]:
        par[u] = v
    else:
        par[v] = u
        if rank[u] == rank[v]:
            rank[v] += 1

def same(u, v):
    u = root(u)
    v = root(v)
    if u == v:
        return 1
    return 0

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

ans = 0
for i in range(N):
    ans += same(i, P[i] - 1)

print(ans)

Submission status: Accepted

Solution code:
from bisect import bisect_left
def rt(i):
    while i!=G[i][0]:
        i = G[i][0]
    return i
N,M = map(int,input().split())
P = list(map(int,input().split()))
P.insert(0,0)
G = {i:[i,1] for i in range(1,N+1)}
for _ in range(M):
    x,y = map(int,input().split())
    rx = rt(x)
    ry = rt(y)
    if rx!=ry:
        if G[rx][1]>=G[ry][1]:
            G[ry][0] = rx
            G[rx][1] += G[ry][1]
        else:
            G[rx][0] = ry
            G[ry][1] += G[rx][1]
hist = [0 for _ in range(N+1)]
A = {}
for i in range(1,N+1):
    ri = rt(i)
    if hist[ri]==0:
        A[ri] = []
        hist[ri] = 1
    A[ri].append(i)
cnt = 0
for a in A:
    B = []
    for i in range(len(A[a])):
        B.append(P[A[a][i]])
    B = sorted(B)
    B.append(10**8)
    cur = 0
    for i in range(len(A[a])):
        if A[a][i]==B[cur]:
            cnt += 1
        elif A[a][i]<B[cur]:
            continue
        else:
            cur = bisect_left(B,A[a][i])
            if B[cur]==A[a][i]:
                cnt += 1
                cur += 1
print(cnt)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        self.data = [-1] * size
    def root(self, x):
        if self.data[x] < 0:
            return x
        ans = self.root(self.data[x])
        self.data[x] = ans
        return ans
    def unite(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return False
        if self.data[x] > self.data[y]:
            x, y = y, x
        self.data[x] += self.data[y]
        self.data[y] = x
        return True
    def same(self, x, y):
        return self.root(x) == self.root(y)
    def size(self, x):
        return -self.data[self.root(x)]

"""
Union-Find 森

https://scrapbox.io/data-structures/Union_Find

UnionFind(size):
0 ~ size - 1 がそれぞれ別々の集合に属するものとして初期化

root(x) -> void:
x が属する集合を表す根付き木の頂点を返す

unite(x) -> Bool:
root(x) と root(y) の間に辺を張り, x が属する集合と y が属する集合を結合する
変更があったかが返る (もともと同じ集合に属していたら False)

same(x, y) -> Bool:
x と y が同じ集合に属するか判定する

size(x) -> Int:
x が属する集合の要素数を返す

実装について
data[x] は data[x] < 0 のとき根であり, data[x] == -size(x) となっています
また, data[x] >= 0 のとき子であり, data[x] は親の番号を表しています
unite(x) は 
if self.data[x] > self.data[y]:
    x, y = y, x
で計算量が落ちます(データ構造をマージする一般的なテク)
root(x) は
self.data[x] = ans
で計算量が落ちます(経路圧縮)
"""


# https://atcoder.jp/contests/arc097/tasks/arc097_b

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

Submission status: Accepted

Solution code:
n,m,*t=map(int,open(0).read().split())
u=[-1]*(n+1)
def root(x):
  while u[x]>=0:x=u[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y:return
  if u[x]>u[y]:x,y=y,x
  u[x]+=u[y]
  u[y]=x
for x,y in zip(*[iter(t[n:])]*2):
  unite(x,y)
print(sum(root(i)==root(p)for i,p in enumerate(t[:n],1)))

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


N, M = map(int, input().split())
uf = UnionFind(N+1)

P = [int(i) for i in input().split()]

for i in range(M):
    x, y = map(int, input().split())
    uf.Unite(x, y)

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