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: Time Limit Exceeded

Solution code:
import math
import random
import heapq
from collections import Counter, defaultdict
from decimal import Decimal, ROUND_HALF_UP, ROUND_CEILING
from functools import lru_cache, reduce
from itertools import combinations_with_replacement, product, combinations


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input()


def read_str_n():
    return list(map(str, input().split()))


def mt(f):
    import time
    import sys

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        print(e - s, 'sec', file=sys.stderr)
        return ret

    return wrap


@mt
def slv(N, M, P, XY):
    P = [-1] + P
    G = []
    for x, y in XY:
        for g in G:
            if x in g or y in g:
                g.add(x)
                g.add(y)
                break
        else:
            G.append(set([x, y]))

    f = True
    while f:
        f = False
        for i, j in combinations_with_replacement(range(len(G)), 2):
            # print(G, i, j)
            if i != j and len(G[i] & G[j]) != 0:
                G[i] = G[i] | G[j]
                G.pop(j)
                f = True
                break

    # print(G)
    ans = 0
    for g in G:
        for x in g:
            if P[x] in g:
                # print(g, x)
                ans += 1

    c = []
    for g in G:
        c += list(g)

    for i in range(1, N + 1):
        if P[i] not in c and P[i] == i:
            ans += 1
    return ans


def main():
    N, M = read_int_n()
    P = read_int_n()
    XY = []
    for _ in range(M):
        XY.append(read_int_n())
    print(slv(N, M, P, XY))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
x=[]
y=[]
ave=[[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):ave[i][i]=1
for _ in range(m):
    X,Y=map(int,input().split())
    ave[X-1][Y-1]=1
    ave[Y-1][X-1]=1
    x.append(X)
    y.append(Y)
do=[]
for i in range(n):
    if(i in do):continue
    queue=[]
    queue.append(i)
    do=[]
    alr=[0 for _ in range(n)]
    while(queue):
        u=queue.pop(0)
        for j in range(n):
            if(i==j):continue
            if(ave[u][j]==1 and alr[j]==0):
                ave[i][j]=1
                ave[j][i]=1
                alr[j]=1
                do.append(j)
                queue.append(j)
    for d in do:
        ave[d]=ave[i]
                
score=n
for i in range(n):
    j=p[i]
    if(ave[i][j-1]==-1):score-=1
print(score)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
import random
import numpy as np
import time


n,m=map(int,input().split())
p=list(map(int,input().split()))
x=[]
y=[]
ave=[[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):ave[i][i]=1
for _ in range(m):
    X,Y=map(int,input().split())
    ave[X-1][Y-1]=1
    ave[Y-1][X-1]=1
    x.append(X)
    y.append(Y)
do=[]
for i in range(n):
    if(i in do):continue
    queue=[]
    queue.append(i)
    do=[]
    alr=[0 for _ in range(n)]
    while(queue):
        u=queue.pop(0)
        for j in range(n):
            if(i==j):continue
            if(ave[u][j]==1 and alr[j]==0):
                ave[i][j]=1
                ave[j][i]=1
                alr[j]=1
                do.append(j)
                queue.append(j)
    for d in do:
        ave[d]=ave[i]
                
score=n
for i in range(n):
    j=p[i]
    if(ave[i][j-1]==-1):score-=1
print(score)

Submission status: Time Limit Exceeded

Solution code:
import sys
from collections import Counter
import random
import numpy as np
import time


n,m=map(int,input().split())
p=list(map(int,input().split()))
x=[]
y=[]
ave=[[-1 for _ in range(n)] for _ in range(n)]
for i in range(n):ave[i][i]=1
for _ in range(m):
    X,Y=map(int,input().split())
    ave[X-1][Y-1]=1
    ave[Y-1][X-1]=1
    x.append(X)
    y.append(Y)
for i in range(n):
    queue=[]
    queue.append(i)
    alr=[0 for _ in range(n)]
    while(queue):
        u=queue.pop(0)
        for j in range(n):
            if(i==j):continue
            if(ave[u][j]==1 and alr[j]==0):
                ave[i][j]=1
                ave[j][i]=1
                alr[j]=1
                queue.append(j)
                
score=n
for i in range(n):
    j=p[i]
    if(ave[i][j-1]==-1):score-=1
print(score)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from bisect import *

def index(a, x):
    'Locate the leftmost value exactly equal to x'
    i = bisect_left(a, x)
    if i != len(a) and a[i] == x:
        return i
    raise ValueError


N,M=map(int, raw_input().split())
p=map(int, raw_input().split())

D=[ [] for x in range(N+1)]

for i in range(M):
    x,y=map(int, raw_input().split())
    D[x].append(y)
    D[y].append(x)

U=list(range( 1,N+1) )
V=[0 for u in range(N+1) ]
A=[]
while(len(U)!=0):
    c=U.pop(0)
    V[c]=1
    a=[c]
    w=D[c]
    while(len(w)!=0):
        ww=w.pop(0)
        if not V[ww]:
            V[ww]=1
            a.append(ww)
            w += [ d for d in D[ww] if V[d]==0 ]
            U.pop(index(U, ww))
    A.append(a)

ans=0
for a in A:
    P =set([p[i-1] for i in a])
    Q =set(a)
    ans+=len( P & Q )
print ans

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

N,M=map(int, raw_input().split())
p=map(int, raw_input().split())

D=[ [] for x in range(N+1)]

for i in range(M):
    x,y=map(int, raw_input().split())
    D[x].append(y)
    D[y].append(x)

U=list(range( 1,N+1) )
V=[0 for u in range(N+1) ]
A=[]
while(len(U)!=0):
    c=U.pop(0)
    V[c]=1
    a=[c]
    w=D[c]
    while(len(w)!=0):
        ww=w.pop(0)
        if not V[ww]:
            V[ww]=1
            a.append(ww)
            w += D[ww]
            U.remove(ww)
    A.append(a)

ans=0
for a in A:
    P =set([p[i-1] for i in a])
    Q =set(a)
    ans+=len( P & Q )
print ans

Submission status: Time Limit Exceeded

Solution code:

def f():
  n,m = (int(i) for i in input().split()) 
  p = [int(i) for i in input().split()]
  s = []
  a = [-i for i in range(n+1)]
  w = [0 for i in range(n+1)]
  for i in range(n):
    w[p[i]] = i+1
  for i in range(m):
    x,y =[int(i) for i in input().split()]
    s.append([x,y])
  # s.sort(key=lambda x:(min(x)))
  # print(s)
  for e in s:
    x,y = e
    z = min(x,y)
    if a[x]<0 and a[y]<0:
      a[x]=z
      a[y]=z
    elif a[x]<0 or a[y]<0:
      z = max(a[x],a[y])
      a[x]=z
      a[y]=z
    else:
      z = min(a[x],a[y])
      zz = max(a[x],a[y])
      a = [ z if ae is zz else ae for ae in a]
    # print(a[1:])
  cnt = 0
  for i in range(1,n+1):
    if a[i] == a[w[i]]:
      cnt += 1
  print(cnt)


f()

Submission status: Time Limit Exceeded

Solution code:
# n = int(input())

# k = [int(i) for i in input().split()]
# 
# cnt = 0
# for i in range(n):
#   sum = 0
#   for j in range(i,n):
#     sum+=a[j]
#     if sum==0:
#       cnt+=1
# print(cnt)
def f():
  n,m = (int(i) for i in input().split()) 
  p = [int(i) for i in input().split()]
  s = []
  a = [-i for i in range(n+1)]
  w = [0 for i in range(n+1)]
  for i in range(n):
    w[p[i]] = i+1
  for i in range(m):
    x,y =[int(i) for i in input().split()]
    s.append([x,y])
  s.sort(key=lambda x:(min(x)))
  # print(s)
  for e in s:
    x,y = e
    z = min(x,y)
    if a[x]<0 and a[y]<0:
      a[x]=z
      a[y]=z
    elif a[x]<0 or a[y]<0:
      z = max(a[x],a[y])
      a[x]=z
      a[y]=z
    else:
      z = min(a[x],a[y])
      zz = max(a[x],a[y])
      a = [ z if ae is zz else ae for ae in a]
    # print(a[1:])
  cnt = 0
  for i in range(1,n+1):
    if a[i] == a[w[i]]:
      cnt += 1
  print(cnt)


f()

Submission status: Time Limit Exceeded

Solution code:


class UnionFind:

    def __init__(self, n):
        self.p = {i: i for i in range(n)}
        self.r = {i: 0 for i in range(n)}

    def root(self, x):
        if self.p[x] == x:
            return x
        self.p[x] = self.root(self.p[x])
        return self.p[x]

    def merge(self, x, y):
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.r[x] == self.r[y]:
            self.r[x] += 1
        elif self.r[x] > self.r[y]:
            x, y = y, x
        self.p[x] = y

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

    def cluster(self):
        c = {}
        for x in self.p:
            xx = self.root(x)
            if xx not in c:
                c[xx] = {x}
            else:
                c[xx].add(x)
        return c


def main():
    n, m = list(map(int, input().split()))
    pp = list(map(int, input().split()))
    uf = UnionFind(n)
    for _ in range(m):
        x, y = map(int, input().split())
        uf.merge(x - 1, y - 1)
    cc = uf.cluster()
    count = 0
    for clt in cc.values():
        p = set(pp[i] - 1 for i in clt)
        count += len(p & clt)
    print(count)


if __name__ == '__main__':
    main()

Submission status: Accepted

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


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

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

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

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

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


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

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

print(res)

Submission status: Accepted

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

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

    def 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 i in range(N):
    if uf.same(i, P[i]-1):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8
import sys

# from operator import itemgetter
sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
printout = sys.stdout.write
sprint = sys.stdout.flush
#from heapq import heappop, heappush
#from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
#import math
# from itertools import product, accumulate, combinations, product
#import bisect
# import numpy as np
# from copy import deepcopy
from collections import deque
# from decimal import Decimal
# from numba import jit

INF = 1 << 50
EPS = 1e-8
mod = 998244353


def intread():
    return int(sysread())
def mapline(t=int):
    return map(t, sysread().split())
def mapread(t=int):
    return map(t, read().split())

def dfs(c, to, seen, G = set()):
    seen.add(c)
    G.add(c)
    for n in to[c]:
        if not n in seen:
            dfs(n, to, G, seen)
    return G


def get_groups(to):
    G = []
    seen = set()
    for i in range(1, len(to)):
        if not i in seen:
            g = dfs(i, to, seen = seen, G = set())
            G.append(g)
    return G

def run():
    N, M = mapline()
    P = deque(list(mapline()))
    P.appendleft(-1)
    to = [[] for _ in range(N+1)]
    for _ in range(M):
        x,y= mapline()
        to[x].append(y)
        to[y].append(x)

    G = get_groups(to)
    ans = 0
    #print(G)
    for g in G:
        for k in g:
            if P[k] in g:
                ans += 1

    print(ans)


if __name__ == "__main__":
    run()

Submission status: Accepted

Solution code:
import sys

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

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


ans = 0
visited = set()
for i in range(N):
    q = [i]
    loop = set()
    values = set()
    while q:
        x = q.pop()
        if x in visited:
            continue
        visited.add(x)
        loop.add(x+1)
        values.add(P[x])

        for nx in edges[x]:
            if nx not in visited:
                q.append(nx)

    ans += len(loop & values)

print(ans)

Submission status: Accepted

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

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.is_same(p[i]-1, i):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
from collections import Counter

class Unionfind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * (n+1)
        
    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)

cnt = sum(uf.same(p[i]-1, i) for i in range(N))
print(cnt)

Submission status: Accepted

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
num=[[] for _ in range(n)]
for i in range(m):
    x,y=map(int,input().split())
    num[x-1].append(y)
    num[y-1].append(x)
seen=[False]*n
ans=list(range(n))
for i in range(n):
    if seen[i]==False:
        queue=[i]
        seen[i]=True
        for j in range(n):
            if len(queue)==0:
                break
            num1=queue.pop()
            ans[num1]=i
            for k in range(len(num[num1])):
                num2=num[num1][k]-1
                if seen[num2]==False:
                    queue.append(num2)
                    seen[num2]=True
ans2=0
for i in range(n):
    if ans[i]==ans[p[i]-1]:
        ans2+=1
print(ans2)

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 same(self, x, y):
    return self.find(x) == self.find(y)

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

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

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

  def num_members(self,x):
    return abs(self.parents[self.find(x)])

  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())
  uf.union(x-1,y-1)
from collections import defaultdict
d = defaultdict(lambda: [])
for i in range(N):
  d[uf.find(i)].append(i)
from bisect import bisect_left
def binary_search(A,p):
  if A[0]<=p and p<=A[-1]:
    if p == A[bisect_left(A,p)]:
      return True
  return False
ans = 0
for v in d.values():
  lis = sorted(v)
  for a in v:
    if binary_search(lis,P[a]-1):
      ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
pn = list(map(lambda x:int(x)-1, input().split()))
ls = [-1] * n
for i in pn:
    ls[pn[i]] = i
par = [i for i in range(n)]
def find(x):
    if par[x] == x:
        return x
    else:
        s = find(par[x])
        par[x] = s
        return s
def unite(x,y):
    s = find(x)
    t = find(y)
    if s>t:
        par[s] = t
    else:
        par[t] = s
for _ in range(m):
    x, y = map(lambda x:int(x)-1, input().split())
    unite(ls[x],ls[y])
ans2 = 0
for i in range(n):
    if find(i)==find(ls[i]):
       ans2+=1
print(ans2)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
pn = list(map(lambda x:int(x)-1, input().split()))
ls = [-1] * n
for i in pn:
    ls[pn[i]] = i
#print(ls)

par = [i for i in range(n)]

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

def unite(x,y):
    s = find(x)
    t = find(y)
    if s>t:
        par[s] = t
    else:
        par[t] = s


for _ in range(m):
    x, y = map(lambda x:int(x)-1, input().split())
    unite(ls[x],ls[y])

ans2 = 0
for i in range(n): 
    place1 = i
    place2 = ls[i]

    if find(place1)==find(place2):
       ans2+=1
print(ans2)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
pn = list(map(lambda x:int(x)-1, input().split()))
ls = [-1] * n
for i in pn:
    ls[pn[i]] = i
#print(ls)

par = [i for i in range(n)]

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

def unite(x,y):
    s = find(x)
    t = find(y)
    if s>t:
        par[s] = t
    else:
        par[t] = s


for _ in range(m):
    x, y = map(lambda x:int(x)-1, input().split())
    unite(ls[x],ls[y])


ans2 = 0
for i in range(n): # i番目の数字がいる場所の親とiの場所
    place1 = ls[pn[i]]
    place2 = ls[i]

    if find(place1)==find(place2):
       ans2+=1
print(ans2)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
pn = list(map(lambda x:int(x)-1, input().split()))
ls = [-1] * n
for i in pn:
    ls[pn[i]] = i
#print(ls)

par = [i for i in range(n)]

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

def unite(x,y):
    s = find(x)
    t = find(y)
    if s>t:
        par[s] = t
    else:
        par[t] = s


for _ in range(m):
    x, y = map(lambda x:int(x)-1, input().split())
    unite(ls[x],ls[y])

dic = {}
for i in range(n):
    a = find(i)
    if a in dic:
        dic[a].add(ls[i])
    else:
        dic[a] = set([ls[i]])
#print(dic)
#print(par)
ans = 0
for i in range(n):
    if i in dic[find(i)]:
       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()))
g = [[] for i in range(n)]
for i in range(m):
  a, b = map(int, input().split())
  g[a-1].append(b-1)
  g[b-1].append(a-1)
v = [-1 for i in range(n)]
s = 0
for i in range(n):
  if v[i]!=-1:
    continue
  s+=1
  v[i]=s
  d = deque([i])
  while len(d):
    x = d.popleft()
    for i in g[x]:
      if v[i] == -1:
        d.append(i)
        v[i]=s
ans=0
for i in range(n):
  if v[i]==v[p[i]-1]:
    ans+=1
print(ans)

Submission status: Accepted

Solution code:
# unionfind
class Uf:
	def __init__(self, N):
		self.p = list(range(N))
		self.rank = [0] * N
		self.size = [1] * N
	#検索 ノード番号を受け取って一番上の親ノードの番号を帰す
	def root(self, x):
		if self.p[x] != x:
			self.p[x] = self.root(self.p[x])

		return self.p[x]
	#同じ集合に属するか判定
	def same(self, x, y):
		return self.root(x) == self.root(y)
	#併合
	def unite(self, x, y):
		# 根を探す
		u = self.root(x)
		v = self.root(y)

		if u == v: return

		#木の高さを比較し、低いほうから高いほうに辺を張る
		if self.rank[u] < self.rank[v]:
			self.p[u] = v
			self.size[v] += self.size[u]
			self.size[u] = 0
		else:
			self.p[v] = u
			self.size[u] += self.size[v]
			self.size[v] = 0
			#木の高さが同じなら片方を1増やす
			if self.rank[u] == self.rank[v]:
				self.rank[u] += 1
	#ノード番号を受け取って、そのノードが含まれている集合のサイズを返す
	def count(self, x):
		return self.size[self.root(x)]

N, M = map(int, input().split())
uf=Uf(N)
P = list(map(int, input().split()))
P=[i-1 for i in P]
for i in range(M):
	x, y = map(int, input().split())
	x-=1
	y-=1
	uf.unite(x,y)

#「値iを含む位置jと位置iが同じグループに属している」という条件を満たすiの数を数える
ans=0
for i in range(N):
	if uf.root(P[i]) == uf.root(i):
		ans+=1
print(ans)

Submission status: Accepted

Solution code:
n,m= map(int,input().split())
par = [-1]*(n)
def find(x):
    if par[x]<0:return x
    else:
        par[x]=find(par[x])
        return par[x]
def unite(x,y):
    px,py=find(x),find(y)
    if px==py:return False
    else:
        if px<py:px,py=py,px
        par[px]+=par[py]
        par[py]=px
        return True
p= list(map(int,input().split()))
gl=[[] for _ in range(n)]
for i in range(m):
    x,y= map(int,input().split())
    unite(x-1,y-1)
for c in range(n):#par:
    ap=find(c)
    gl[ap].append(c)
g=0
for sg in gl:
    temp=[p[index]-1 for index in sg]
    newset = set(sg) & set(temp)
    g+=len(newset)
print(g)

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

def main():
    N, M = map(int, input().split())
    P = list(map(int, input().split()))
    uni = UnionFind(N)

    for i in range(N):
        P[i] -= 1

    for _ in range(M):
        x, y = map(int, input().split())
        x -= 1
        y -= 1
        uni.union(x,y)
    ans = 0
    for i in range(N):
        if P[i] == i:
            ans += 1
        else:
            if uni.same(i,P[i]):
                ans += 1

    print(ans)



if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
class Unionfind():  # 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 groups(self):  # 全てのグループごとの要素
        members_dict = {i: set() for i, x in enumerate(self.parents) if x < 0}
        for i in range(self.N):
            members_dict[self.find(i)].add(i)
        return members_dict


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

uf = Unionfind(n)
for x, y in xy:
    uf.union(x - 1, y - 1)

ans = 0
for lst in uf.groups().values():
    ans += sum((p[num] - 1 in lst) for num in lst)
print(ans)

Submission status: Accepted

Solution code:
class Unionfind():  # 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 groups(self):  # 全てのグループごとの要素
        members_dict = {}
        for i in range(self.N):
            if self.find(i) not in members_dict:
                members_dict[self.find(i)] = set()
            members_dict[self.find(i)].add(i)
        return members_dict


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

uf = Unionfind(n)
for x, y in xy:
    uf.union(x - 1, y - 1)

ans = 0
for lst in uf.groups().values():
    ans += sum((p[num] - 1 in lst) for num in lst)
print(ans)

Submission status: Accepted

Solution code:
class Unionfind():  # 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 all_group_members(self):  # グループごとの辞書
        members_dict = {i: set([i]) for i, x in enumerate(self.parents) if x < 0}
        for i, x in enumerate(self.parents):
            if x >= 0:
                members_dict[self.find(x)].add(i)
        return members_dict


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

uf = Unionfind(n)
for x, y in xy:
    uf.union(x - 1, y - 1)

ans = 0
for lst in uf.all_group_members().values():
    ans += sum((p[num] - 1 in lst) for num in lst)
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 same(x,y):
    return find(x) == find(y)
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return 0
    par[x] = y
    size[y] = size[x] + size[y]
    size[x] = 0

N,M = list(map(int, input().split()))
plist = list(map(int,input().split()))
ABs = [list(map(int, input().split())) for _ in range(M)]
par = [i for i in range(N+1)]
size = [1 for _ in range(N+1)]

for AB in ABs:
    unite(AB[0],AB[1])

Ans = 0
for i in range(len(plist)):
    if plist[i] == i+1:
        Ans +=1
    else:
        if same(plist[i],i+1):
            Ans += 1
print(Ans)