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
input = sys.stdin.readline
n, m = map(int, input().split())
P = list(map(int, input().split()))


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

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

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx != ry:
            if self.r[rx] > self.r[ry]:
                rx, ry = ry, rx
            if self.r[rx] == self.r[ry]:
                self.r[ry] += 1
            self.p[ry] += self.p[rx]
            self.p[rx] = ry

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


uf = UnionFind(n)
for _ in range(m):
    x, y = list(map(lambda x: int(x)-1, input().split()))
    uf.union(x, y)

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

Submission status: Accepted

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

par = {x:x for x in range(1, n+1)}

def root(node):
    if par[node] == node:
        return node
    par[node] = root(par[node])
    return par[node]

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

print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(pow(10,9))
class UnionFind():
    def __init__(self,n):
        self.root = [-1]*n
        self.rank = [1]*n
    def find(self,x):
        if self.root[x] < 0:
            return x
        else:
            self.root[x] = self.find(self.root[x])
            return self.find(self.root[x])
    def union(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.root[y] = x

N,M = map(int,input().split())
P = list(map(lambda x:int(x)-1,input().split()))
T = UnionFind(N)
for i in range(M):
    x,y = map(lambda x:int(x)-1,input().split())
    T.union(x,y)
cnt = 0
for i in range(N):
    p = P[i]
    if T.find(i)==T.find(p):
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
#各pは、自分の今いるインデックスがindex p-1と繋がっていればそこに移動する
import sys
sys.setrecursionlimit(200000)

class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)
    def find(self,x):
        if self.parents[x]==x:
            return x
        else:
            self.parents[x]=self.find(self.parents[x])
            return self.parents[x]
    def unite(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1
N,M = map(int,input().split())
P = list(map(int,input().split()))
tree = UnionFind(N)
for _ in range(M):
    x,y = map(int,input().split())
    tree.unite(x,y)

count = 0
for i in range(N):
    if tree.find(i+1) == tree.find(P[i]):
        count += 1

print(count)

Submission status: Accepted

Solution code:
# ARC097D

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))

n, m = map(int, input().split())
p = list(map(lambda x: int(x)-1, input().split()))
from collections import defaultdict
es = defaultdict(set)
for i in range(m):
    u,v = map(int, input().split())
    es[u-1].add(v-1)
    es[v-1].add(u-1)
    
count = 0
seen = [False] * n
for u in range(n):
    index = set()
    values = set()
    if seen[u]:
        continue
    index.add(u)
    values.add(p[u])
    q = [u]
    seen[u] = True
    while q:
        u = q.pop()
        for v in es[u]:
            if not seen[v]:
                q.append(v)
                seen[v] = True
                index.add(v)
                values.add(p[v])
    count += len(index & values)
print(count)

Submission status: Accepted

Solution code:
import numpy as np
n,m = map(int,input().split())
lis = list(map(int,input().split()))
path = [[] for i in range(n)]

for i in range(m):
    x,y = map(int,input().split())
    x -= 1;y -= 1
    path[x].append(y)
    path[y].append(x)

gone = np.array([-1] * n)
numberindex = set()
realnumber = set()
ans = 0

for i in range(n):
    if gone[i] == -1:
        now = [i]
        while now:
            a = now.pop(0)
            gone[a] = 1
            numberindex.add(a)
            realnumber.add(lis[a]-1)
            for go in path[a]:
                if gone[go] == -1:
                    now.append(go)
                    gone[go] = 1
        ans += len(realnumber & numberindex)
        realnumber,numberindex = set(),set()
print(ans)

Submission status: Accepted

Solution code:
from collections import defaultdict

class UnionFind(object):
  def __init__(self, n=1):
    self.par = [i for i in range(n)]
    self.rank = [0 for _ in range(n)]
    self.size = [1 for _ in range(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 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.par[y] = x
      self.size[x] += self.size[y]
  def is_same(self, x, y):
    return self.find(x) == self.find(y)
  def get_size(self, x):
    x = self.find(x)
    return self.size[x]


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

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

z = []
for i in range(M):
  t, s = map(int,input().split())
  z.append((t,s))

uf = UnionFind(N)

for i in range(M):
  uf.union(z[i][0]-1, z[i][1]-1) #1というのは0番目のため1を引く。

#c = defaultdict(int)
ans = 0
for i in range(N):
  if uf.is_same(i, P[i]-1):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)

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

    def union(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1

N,M = map(int,input().split())
tree = UnionFind(N)
P = list(map(int,input().split()))
for _ in range(M):
    x,y = map(int,input().split())
    tree.union(x,y)

indeces = {}
indeces2 = {}
for i in range(N):
    indeces[P[i]]=i+1
    indeces2[i+1]=P[i]

group = {}
group2 = {}
for i in range(1,N+1):
    r = tree.find(i)
    if r not in group:
        group[r]=set()
    group[r].add(i)
    group2[i]=r

ans = 0
for n,index in indeces.items():
    if n == index:
        ans += 1
    else:
        groupNum = group2[index]
        if n in group[groupNum]:
            ans += 1
            a = indeces2[n] #n番目に現在君臨している数字
            indeces2[n] = n
            indeces2[index] = a
            indeces[a] = index
            indeces[n] = n

print(ans)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
r=[i for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    return
  else:
    r[rx]=ry
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
for i in range(m):
  a,b=map(int,input().split())
  union(a-1,b-1)
ans=0
for i in range(n):
  if root(i)==root(p[i]-1) or i+1==p[i]:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2000000)
input = sys.stdin.readline
class UnionFind():
    def __init__(self,n):
        self.n=n
        self.parents = [i for i in range(n+1)]
        self.size = [1]*(n+1)

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

    def union(self,x,y):
        xRoot = self.find(x)
        yRoot = self.find(y)
        if xRoot == yRoot:
            return
        if self.size[xRoot]>self.size[yRoot]:
            self.parents[yRoot] = xRoot
        else:
            self.parents[xRoot] = yRoot
            if self.size[xRoot] == self.size[yRoot]:
                self.size[yRoot]+=1

N,M = map(int,input().split())
P = list(map(int,input().split()))
dic = {}
dic2 = {}
for i in range(1,N+1):
    dic[P[i-1]]=i
    dic2[i]=P[i-1]

tree = UnionFind(N)
for _ in range(M):
    x,y = map(int,input().split())
    tree.union(x,y)

indexGroup = {}
for i in range(1,N+1):
    root = tree.find(i)
    if root not in indexGroup:
        indexGroup[root]=set()
    indexGroup[root].add(i)

for p,i in dic.items():
    root = tree.find(i)
    if p in indexGroup[root]:
        n = dic2[p]
        dic[p] = p
        dic2[p] = p
        dic[n] = i
        dic2[i] = n

count = 0
for p,i in dic.items():
    if p==i:
        count += 1
print(count)

Submission status: Accepted

Solution code:
import sys,queue,math,copy,itertools,bisect,collections,heapq
LI = lambda : [int(x) for x in sys.stdin.readline().split()]
NI = lambda : int(sys.stdin.readline())

N,M = LI()
p = [0] + LI()

g = [i for i in range(N+1)]
g_num = [1 for _ in range(N+1)]

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

def union(x,y):
    if find(x) == find(y): return
    if g_num[g[x]] < g_num[g[y]]: x,y = y,x
    g_num[g[x]] += g_num[g[y]]
    g[g[y]] = g[x]

for _ in range(M):
    x,y = LI()
    union(x,y)

ans = 0
for i in range(1,N+1): ans += (find(i)==find(p[i]))
print(ans)

Submission status: Accepted

Solution code:
def find(x):
    if(par[x]==x):
        return x
    else:
        par[x]=find(par[x])
        return par[x]
def union(a,b):
    a=find(a)
    b=find(b)
    if(a==b):
        return 0
    else:
        if rank[a]>rank[b]:
            par[b]=a
            siz[a]+=siz[b]
        else:
            par[a]=b
            siz[b]+=siz[a]
            if rank[a]==rank[b]:
                rank[b]+=1
def size(a):
    return siz[find(a)]
def same(a,b):
    return find(a)==find(b)
    
N,M=map(int,input().split())
par=[i for i in range(N)]
siz=[1 for _ in range(N)]
rank=[0 for _ in range(N)]

p=list(map(lambda x:int(x)-1,input().split()))
dic={p[i]:i for i in range(N)}

for i in range(M):
    x,y=map(lambda x:int(x)-1,input().split())
    union(dic[x],dic[y])
cnt=0
for i in range(N):
    if same(i,p[i]):
        cnt+=1
print(cnt)

Submission status: Accepted

Solution code:
from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))


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()}
n,m = inpl()
a = inpl()
uf = UnionFind(n)
for i in range(m):
    x,y = inpl()
    x -= 1; y -= 1
    uf.union(x,y)
res = 0
for i in range(n):
    if uf.same(a[i]-1, i):
        res += 1
print(res)

Submission status: Accepted

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


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


uf = UnionFind(n)
for i in range(m):
    a, b = list(map(int, input().split()))
    uf.union(a-1, b-1)

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

Submission status: Accepted

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

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

uf = UnionFind(n)

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

ans = 0
for idx, p in enumerate(pl):
    if uf.same(idx, p-1):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import deque
N,M = map(int,input().split())
P = list(map(int,input().split()))
P.insert(0,0)
G = {i:[] for i in range(1,N+1)}
for _ in range(M):
    x,y = map(int,input().split())
    G[x].append(y)
    G[y].append(x)
A = []
hist = [0 for _ in range(N+1)]
for i in range(1,N+1):
    if hist[i]==0:
        C = [i]
        hist[i]=1
        que = deque([i])
        while que:
            x = que.popleft()
            for y in G[x]:
                if hist[y]==0:
                    que.append(y)
                    C.append(y)
                    hist[y]=1
        C = sorted(C)
        A.append(C)
cnt = 0
for C in A:
    B = []
    for c in C:
        B.append(P[c])
    B = sorted(B)
    cur = 0
    for i in range(len(C)):
        if cur<len(B) and C[i]==B[cur]:
            cnt += 1
            cur += 1
        elif cur<len(B) and C[i]<B[cur]:
            continue
        elif cur<len(B) and C[i]>B[cur]:
            while cur<len(B) and C[i]>B[cur]:
                cur += 1
            if cur<len(B) and B[cur]==C[i]:
                cnt += 1
            else:
                continue
print(cnt)

Submission status: Accepted

Solution code:
N,M=map(int, input().split())
P=list(map(int, input().split()))
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を見てくっつける方を決める
      #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)]
uni=UnionFind(N)

for i in range(M):
    x,y=map(int, input().split())
    uni.Unite(x-1,y-1)
ans=0    
for i,p in enumerate(P):
  if uni.isSameGroup(i,p-1):
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
# import string
import sys
sys.setrecursionlimit(10 ** 5 + 10)
def input(): return sys.stdin.readline().strip()

def resolve():


    class UnionFind(object):
        def __init__(self, n=1):
            # 木の親要素を管理するリストparをつくります。
            # par[x] == xの場合には、そのノードが根であることを示します。
            # 初期状態では一切グループ化されていないので、すべてのノードが根になりますね。
            self.par = [i for i in range(n)]
            # 木の高さを持っておき、あとで低い方を高い方につなげる。初期状態は0
            self.rank = [0 for _ in range(n)]
            self.size = [1 for _ in range(n)]

        def find(self, x):
            """
            x が属するグループを探索：
            ある２つの要素が属する木の根が同じかどうかをチェックすればよい。
            つまり、親の親の親の・・・と根にたどり着くまで走査すればよい。
            再帰。
            """
            # 根ならその番号を返す
            if self.par[x] == x:
                return x
            # 根でないなら、親の要素で再検索
            else:
                # 一度見た値については根に直接繋いで経路圧縮
                # 親を書き換えるということ
                self.par[x] = self.find(self.par[x])
                return self.par[x]

        def union(self, x, y):
            """
            x と y のグループを結合
            """
            # 根を探す
            x = self.find(x)
            y = self.find(y)
            # 小さい木に結合して経路圧縮
            if x != y:
                if self.rank[x] < self.rank[y]:
                    x, y = y, x
                # 同じ長さの場合rankが1増える
                if self.rank[x] == self.rank[y]:
                    self.rank[x] += 1
                # 低い方の木の根を高い方の根とする
                self.par[y] = x
                self.size[x] += self.size[y]

        def is_same(self, x, y):
            """
            x と y が同じグループか否か
            """
            return self.find(x) == self.find(y)

        def get_size(self, x):
            """
            x が属するグループの要素数
            """
            x = self.find(x)
            return self.size[x]

    N, M = map(int, input().split())
    uf = UnionFind(N)  # ノード数Nでクラス継承
    l=list(map(int,input().split()))

    for i in range(M):
        # A,Bはノード
        A, B = map(int, input().split())
        A,B=A-1,B-1
        uf.union(A, B)
    cnt=0
    for i in range(N):
        if uf.is_same(l[i]-1,i):
            cnt+=1
    print(cnt)

resolve()

Submission status: Accepted

Solution code:
class UnionFind :
    def __init__(self, size) :
        self.parent = list(range(size))
        self.height = [0] * size
        self.size = [1] * size
        self.component = size

    def root(self, index) :
        if self.parent[index] == index :  # 根の場合
            return index
        rootIndex = self.root(self.parent[index])  # 葉の場合親の根を取得
        self.parent[index] = rootIndex  # 親の付け直し
        return rootIndex

    def union(self, index1, index2) :  # 結合
        root1 = self.root(index1)
        root2 = self.root(index2)

        if root1 == root2 :  # 連結されている場合
            return

        self.component -= 1  # 連結成分を減らす

        if self.height[root1] < self.height[root2] :
            self.parent[root1] = root2  # root2に結合
            self.size[root2] += self.size[root1]
        else :
            self.parent[root2] = root1  # root1に結合
            self.size[root1] += self.size[root2]
            if self.height[root1] == self.height[root2] :
                self.height[root1] += 1
        return

    def isSameRoot(self, index1, index2) :
        return self.root(index1) == self.root(index2)

    def sizeOfSameRoot(self, index) :
        return self.size[self.root(index)]

    def getComponent(self) :
        return self.component

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

tree = UnionFind(N)
for _ in range(M):
    fr, to = map(int, input().split())
    tree.union(fr - 1, to - 1)

ans = 0
for i, p in enumerate(P):
    ans += tree.isSameRoot(i, p)
print(ans)

Submission status: Accepted

Solution code:
def main():
    import sys
    input = sys.stdin.buffer.readline
    N, M = (int(i) for i in input().split())
    P = [int(i)-1 for i in input().split()]
    XY = [[int(i)-1 for i in input().split()] for j in range(M)]

    par = [i for i in range(N)]
    rank = [1 for i in range(N)]

    def find_root(x):
        if par[x] == x:
            return x
        else:
            par[x] = find_root(par[x])
            return par[x]

    def is_same_group(x, y):
        return find_root(x) == find_root(y)

    def unite(x, y):
        x = find_root(x)
        y = find_root(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            x, y = y, x
        rank[x] += rank[y]
        par[y] = x

    def size(x):
        return rank[find_root(x)]

    for x, y in XY:
        unite(x, y)

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


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
def main():
    input = sys.stdin.readline
    N,M=map(int, input().split())
    *P,=map(int, input().split())
    P=[0]+P
    uf=UnionFindTree(N+1)
    for _ in range(M):
        x,y=map(int, input().split())
        uf.union(x,y)
    ans=0
    for i in range(1,N+1):
        if uf.same(i,P[i]): ans+=1
    print(ans)

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

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

    def union(self, x, y):
        x, y, p = self.find(x), self.find(y), self.parent
        if x == y: return False
        if p[x] > p[y]: x, y = y, x
        p[x], p[y] = p[x] + p[y], x
        return True

    def same(self, x, y): return self.find(x) == self.find(y)
    def size(self, x): return -self.parent[self.find(x)]

if __name__ == '__main__':
    main()

Submission status: Accepted

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


class UnionFind(object):
    def __init__(self, N):
        self.parent = [-1] * N #parent[i] は(i+1)番目の要素が含まれる要素数の(-1)倍
    #要素が負-->その数を親とするグループに属する要素の数×(-1)
    #要素が正-->親のindex

    #Aがどのグループに属しているかを調べる
    def root(self, A):
        if self.parent[A-1] < 0: #負の数-->その数は親
            return A
        self.parent[A-1] = self.root(self.parent[A-1]) #負では無い時、親の場所が入っているから、親が属しているグループを、自分自身に入れる(一度確認したところは直接親を見れるようにする)
        return self.parent[A-1] #親の位置を返す

    #Aが含まれているグループに属している数を返す
    def size(self, A):
        return -1 * self.parent[self.root(A)-1]

    #AとBをくっ付ける
    def connect(self, A, B):
        A = self.root(A) #Aを含むグループの親を返す
        B = self.root(B) #Bを含むグループの親を返す
        if A == B: #親が同じならなにもしない
            return False
        
        #大きい方(A)に小さい方(B)をつなぎたい
        if self.size(A) < self.size(B): #大小関係が逆の時は入れ替える
            A, B = B, A
        
        self.parent[A-1] += self.parent[B-1] #大きい方に小さい方を加える　（負の数＋負の数 = 新しいグループに含まれる数×(-1)）
        self.parent[B-1] = A #加えられた親の値を、加えた先の親の位置に書き変える
        return True
    
    def same(self, A, B):
        if self.root(A) == self.root(B):
            return True
        else:
            return False

uni = UnionFind(N + 1)

for _ in range(M):
    x, y = map(int, input().split())
    uni.connect(x, y)

count = 0

for index, p in enumerate(P):
    if uni.same(p, index + 1):
        count += 1

print (count)

Submission status: Accepted

Solution code:
from collections import deque


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

info = [list(map(int, input().split())) for i in range(m)]
graph = [[] for i in range(n)]
for a, b in info:
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)
    

used = [False] * n
def dfs(i):
    q = deque([i])
    used[i] = True
    set_ = set([i])
    ans = 0
    while q:
        v = q.pop()
        for nxt_v in graph[v]:
            if used[nxt_v]:
                continue
            used[nxt_v] = True
            q.append(nxt_v)
            set_.add(nxt_v)
    for i in set_:
        if p[i] - 1 in set_:
            ans += 1
    return ans

res = 0
for i in range(n):
    if used[i]:
        continue
    else:
        res += dfs(i)
print(res)

Submission status: Accepted

Solution code:
#-----UnionFind-----(0-indexed)
import sys;sys.setrecursionlimit(10**9)
class UnionFind:
  def __init__(self,n):
    self.n=[-1]*n
    self.r=[0]*n
    self.siz=n
  def find_root(self,x):
    if self.n[x]<0:
      return x
    else:
      self.n[x]=self.find_root(self.n[x])
      return self.n[x]
  def unite(self,x,y):
    x=self.find_root(x)
    y=self.find_root(y)
    if x==y:return
    elif self.r[x]>self.r[y]:
      self.n[x]+=self.n[y]
      self.n[y]=x
    else:
      self.n[y]+=self.n[x]
      self.n[x]=y
      if self.r[x]==self.r[y]:
        self.r[y]+=1
    self.siz-=1
  def root_same(self,x,y):
    return self.find_root(x)==self.find_root(y)
  def count(self,x):
    return -self.n[self.find_root(x)]
  def size(self):
    return self.siz

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

Submission status: Accepted

Solution code:
class UnionFind:

    def __init__(self, n):
        self.parents = [i for i in range(n + 1)]
        self.ranks = [0 for _ in range(n + 1)]

    def find_root(self, node):
        parent_node = self.parents[node]
        if node == parent_node:
            return node
        else:
            root_node = self.find_root(parent_node)
            self.parents[node] = root_node  # reduction
            return root_node

    def union(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        if one_root == other_root:
            return
        one_rank = self.ranks[one_root]
        other_rank = self.ranks[other_root]
        if one_rank < other_rank:
            self.parents[one_root] = other_root
        else:
            self.parents[other_root] = one_root
            if one_rank == other_rank:
                self.ranks[other_root] += 1

    def is_same_group(self, one, other):
        one_root = self.find_root(one)
        other_root = self.find_root(other)
        return one_root == other_root


def main():
    N, M = list(map(int, input().split(' ')))
    p = list(map(int, input().split(' ')))
    tree = UnionFind(N)
    for _ in range(M):
        x, y = list(map(int, input().split(' ')))
        tree.union(p[x - 1], p[y - 1])
    answer = 0
    for i in range(1, N + 1):
        if tree.is_same_group(i, p[i - 1]):
            answer += 1
    print(answer)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def main():
    N, M = (int(_) for _ in input().split())
    P = [int(_) for _ in input().split()]
    swap = [[int(_) for _ in input().split()] for __ in range(M)]

    par = [i for i in range(N+1)]
    rank = [0] * (N+1)

    # 要素xの親ノードを返す
    def find(x):
        if par[x] == x:
            return x
        par[x] = find(par[x])
        return par[x]

    # 要素x, yの属する集合を併合
    def unite(x, y):
        x, y = find(x), find(y)
        if x == y:
            return
        if rank[x] < rank[y]:
            par[x] = y
        else:
            par[y] = x
            if rank[x] == rank[y]:
                rank[x] += 1
        return

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

    for a, b in swap:
        unite(a, b)

    ret = 0
    for i, p in enumerate(P, 1):
        if same(i, p): ret += 1
    print(ret)
    return

if __name__ == '__main__':
    main()