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:
n,m=map(int,input().split())
p=list(map(int,input().split()))
rank=[0 for i in range(n)]
r=[i for i in range(n)]
sp=[{p[i]-1} for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    sp[rx]=sp[rx]|sp[ry]
  else:
    r[ry]=rx
    sp[rx]=sp[rx]|sp[ry]
    if r[rx]==r[ry]:
      rank[rx]+=1
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def get(x):
  return sp[root(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 (i in get(i)) or i+1==p[i]:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
p=list(map(int,input().split()))
rank=[0 for i in range(n)]
r=[i for i in range(n)]
si=[{i} for i in range(n)]
sp=[{p[i]-1} for i in range(n)]
def union(x,y):
  rx=root(x)
  ry=root(y)
  if rx==ry:
    si[rx]=si[ry]|si[rx]
    sp[rx]=sp[rx]|sp[ry]
  else:
    r[ry]=rx
    si[rx]=si[rx]|si[ry]
    sp[rx]=sp[rx]|sp[ry]
    if r[rx]==r[ry]:
      rank[rx]+=1
def root(x):
  if x==r[x]:
    return x
  else:
    r[x]=root(r[x])
    return r[x]
def get(x):
  return sp[root(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 (i in get(i)) or i+1==p[i]:
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin

[N, M] = [int(x) for x in stdin.readline().rstrip().split()]
Ps = [int(x)-1 for x in stdin.readline().rstrip().split()]
X = []
Y = []

for i in range(M):
    [x, y] = [int(x) for x in stdin.readline().rstrip().split()]
    X.append(x-1)
    Y.append(y-1)


def find_root(i,parent):
    path_element = []
    while(True):
        if parent[i] == i:
            #その途中の要素の親も変える
            for j in range(len(path_element)):
                parent[path_element[j]] = i
            return i
        else:
            path_element.append(i)
            i = parent[i]

def merge_tree(i,j,parent): #iとjが所属する木を合成する
    #最初にiとjが同じ気に木していないかをチェックする
    i_root = find_root(i,parent)
    j_root = find_root(j,parent)
    if j_root == i_root:
        #同じだったら何もしない
        return
    else:
        #違う場合にはjの根をiの根に繋ぎ変える
        if (i + j)%2==0:
            parent[j_root] = i_root
        else:
            parent[i_root] = j_root
        return

parent_tree = [i for i in range(N)]

for i in range(M):
    merge_tree(X[i],Y[i],parent_tree)

for i in range(N):
    find_root(i,parent_tree)

#print(Ps)
#print(parent_tree)

temp_map = {}
for i in range(N):
    if parent_tree[i] in temp_map.keys():
        temp_map[parent_tree[i]].append(i)
    else:
        temp_map[parent_tree[i]] = [i]

total_num = 0
for i in range(N):
    if Ps[i] in temp_map[parent_tree[i]]:
        total_num += 1

print(total_num)

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
root=[i for i in range(n+1)]
rank=[0]*(n+1)
def find(x):
    if x==root[x]:
        return x 
    else:
        return find(root[x])

def union(x1,y1):
    x=find(x1)
    y=find(y1)
    if rank[x]>rank[y]:
        root[y]=x 
    elif rank[x]<=rank[y]:
        root[x]=y
        if rank[x]==rank[y]:
            rank[y]+=1
def k_sub():    
    p=list(map(int,input().split()))
    p=[-1]+p 
    for _ in range(m):
        x,y=map(int,input().split())
        union(x,y)
    d=[[] for i in range(n+1)]
    u=[[] for i in range(n+1)]
    for i in range(1,n+1):
        d[find(i)].append(i)
        u[find(i)].append(p[i])
    cnt=0
    for i in range(1,n+1):
        for candidate in d[i]:
            cnt+=(candidate in u[i])
    print(cnt)
if __name__=='__main__':
    k_sub()

Submission status: Time Limit Exceeded

Solution code:
n,m=map(int,input().split())
root=[i for i in range(n+1)]
rank=[0]*(n+1)
def find(x):
    if x==root[x]:
        return x 
    else:
        return find(root[x])

def union(x1,y1):
    x=find(x1)
    y=find(y1)
    if rank[x]>rank[y]:
        root[y]=x 
    elif rank[x]<=rank[y]:
        root[x]=y
        if rank[x]==rank[y]:
            rank[y]+=1
def k_sub():    
    p=list(map(int,input().split()))
    p=[-1]+p 
    for _ in range(m):
        x,y=map(int,input().split())
        union(x,y)
    d=[[] for i in range(n+1)]
    u=[[] for i in range(n+1)]
    for i in range(1,n+1):
        d[find(i)].append(i)
        u[find(i)].append(p[i])
    cnt=0
    for i in range(1,n+1):
        #print(d[i])
        for candidate in d[i]:
            if candidate in u[i]:
                cnt+=1
    print(cnt)
if __name__=='__main__':
    k_sub()

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import permutations,combinations
from collections import defaultdict,Counter
from pprint import pprint

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

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col):
    data.sort(key=lambda x:x[col],reverse=False)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

class UnionFind():
    # parentsは「要素が根の場合に"そのグループの要素数*(-1)"を格納するリスト」
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    # 要素xが属するgroupの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    # 要素xが属するgroupと要素yが属するgroupを併合する
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

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

        self.parents[x] += self.parents[y]
        self.parents[y] = x
    # 要素xが属するgroupのサイズ（要素数）を返す
    def size(self, x):
        return -self.parents[self.find(x)]
    # 要素x,yが同じgroupに属するかをTrueかFalseで返す
    def same(self, x, y):
        return self.find(x) == self.find(y)
    # 要素xが属するgroupに属する要素をリストで返す
    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]
    # groupの数を返す
    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 = myinput()
p = list(myinput())
xy = [ list(myinput()) for _ in range(m) ]

uf = UnionFind(n)

for i in range(m):
    x = xy[i][0] - 1
    y = xy[i][1] - 1
    uf.union(x,y)

# print(uf.group_count())

# ls_uf = uf.all_group_members()
# print(ls_uf)

count = 0
for i in range(n):
    tmp = p[i] - 1
    if tmp==i:
        pass
    else:
        ls = uf.members(i)
        if tmp in ls:
            pass
        else:
            count += 1
# print(count)
ans = n - count
print(ans)

Submission status: Time Limit Exceeded

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


n, m = map(int, input().split())
p_list = list(map(int, input().split()))
q_list = []
for item in p_list:
    q_list.append(item-1)

uni = UnionFind(n)

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

ret = 0

tmp_dict = uni.all_group_members()

for item in tmp_dict:
    t_list = tmp_dict[item]
    tmp = set()
    for var in t_list:
        tmp.add(q_list[var])
    ret += len(tmp & set(t_list))

print(ret)

Submission status: Time Limit Exceeded

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


n, m = map(int, input().split())
p_list = list(map(int, input().split()))
q_list = []
for item in p_list:
    q_list.append(item-1)

uni = UnionFind(n)

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

ret = 0

tmp_dict = uni.all_group_members()

for item in tmp_dict:
    t_list = tmp_dict[item]
    tmp = []
    for var in t_list:
        tmp.append(q_list[var])
    ret += len(set(tmp) & set(t_list))

print(ret)

Submission status: Time Limit Exceeded

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


n, m = map(int, input().split())
p_list = list(map(int, input().split()))
q_list = []
for item in p_list:
    q_list.append(item-1)

uni = UnionFind(n)

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

ret = 0

for item in uni.all_group_members():
    t_list = uni.all_group_members()[item]
    tmp = []
    for var in t_list:
        tmp.append(q_list[var])
    ret += len(set(tmp) & set(t_list))

print(ret)

Submission status: Time Limit Exceeded

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


def unite(par, i, j):
    j = get_par(par, j)
    par[j] = get_par(par, i)

def get_par(par, p):
    while par[p] != p:
        p = par[p]
    return par[p]


n,m = map(int, input().split())
p = list(map(int, input().split()))
par = [i for i in range(n+1)]

for i in range(m):
    a,b = map(int, input().split())
    aa = get_par(par, a)
    bb = get_par(par, b)
    if aa == bb:
        continue
    # unite
    unite(par, a, b)

ans = 0
for i in range(n):
    a = p[i]
    if get_par(par, a) == get_par(par, i+1):
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n, p):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n
        # one -index
        self.g  = [set([i]) for i in range(n+1)]
        self.gp = [set([i]) for i in p]

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.g[y+1] = self.g[y+1] | self.g[x+1]
            self.gp[y+1]= self.gp[y+1]| self.gp[x+1]
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

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

def main():
    n,m = map(int,input().split())
    p = [0] + list(map(int,input().split()))

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

    parent = [False]*n
    ans = 0
    for i in range(n):
        j = uf.find(i)
        if not parent[j]:
            parent[j] = True
            ans += len(uf.g[j+1]) + len(uf.gp[j+1]) - len(uf.g[j+1] | uf.gp[j+1])
    # ans = 0
    # for j in parent:
    #     ans += len(uf.g[j+1]) + len(uf.gp[j+1]) - len(uf.g[j+1] | uf.gp[j+1])
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n, p):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n
        # one -index
        self.g  = [set([i]) for i in range(n+1)]
        self.gp = [set([i]) for i in p]

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.g[y+1] = self.g[y+1] | self.g[x+1]
            self.gp[y+1]= self.gp[y+1]| self.gp[x+1]
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

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

def main():
    n,m = map(int,input().split())
    p = [0] + list(map(int,input().split()))

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

    parent = set()
    for i in range(n):
        parent.add(uf.find(i))
    ans = 0
    for i in parent:
        ans += len(uf.g[i+1]) + len(uf.gp[i+1]) - len(uf.g[i+1] | uf.gp[i+1])
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n
        # one -index
        # self.g  = [set([i]) for i in range(n+1)]
        # self.gp = [set([i]) for i in p]

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # self.g[y+1] = self.g[y+1] | self.g[x+1]
            # self.gp[y+1]= self.gp[y+1]| self.gp[x+1]
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

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

def main():
    n,m = map(int,input().split())
    p = [set([int(i)]) for i in input().split()]
    r = [set([int(i)]) for i in range(1,n+1)]
    uf = UnionFind(n)
    for i in range(m):
        x,y = map(int,input().split())
        uf.unite(x-1,y-1)
    parent = set()
    for i in range(n):
        parent.add(uf.find(i))
        p[uf.find(i)] = p[uf.find(i)] | p[i]
        r[uf.find(i)] = r[uf.find(i)] | r[i]

    ans = 0
    for i in parent:
        ans += len(p[i]) + len(r[i]) - len(p[i] | r[i])
    print(ans)
main()

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n
        # one -index
        # self.g  = [set([i]) for i in range(n+1)]
        # self.gp = [set([i]) for i in p]

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            # self.g[y+1] = self.g[y+1] | self.g[x+1]
            # self.gp[y+1]= self.gp[y+1]| self.gp[x+1]
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

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


n,m = map(int,input().split())
p = [set([int(i)]) for i in input().split()]
r = [set([int(i)]) for i in range(1,n+1)]
uf = UnionFind(n)
for i in range(m):
    x,y = map(int,input().split())
    uf.unite(x-1,y-1)
parent = set()
for i in range(n):
    parent.add(uf.find(i))
    p[uf.find(i)] = p[uf.find(i)] | p[i]
    r[uf.find(i)] = r[uf.find(i)] | r[i]

ans = 0
for i in parent:
    ans += len(p[i]) + len(r[i]) - len(p[i] | r[i])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class UnionFind:
    def __init__(self, n, p):
        '木の初期化をする'
        # zero-index
        self.p  = [-1] * n
        self.rank = [1]*n
        # one -index
        self.g  = [set([i]) for i in range(n+1)]
        self.gp = [set([i]) for i in p]

    def find(self, x):
        'x の親を返す'
        if self.p[x] == -1:
            return x
        else:
            self.p[x] = self.find(self.p[x])
            return self.p[x]

    def unite(self, x, y):
        'rankの低い親を高い方のの親にする'
        if not self.same(x,y):
            x = self.find(x)
            y = self.find(y)
            if self.rank[x] > self.rank[y]:
                x,y = y,x
            elif self.rank[x] == self.rank[y]:
                self.rank[x] += 1
            self.g[y+1] = self.g[y+1] | self.g[x+1]
            self.gp[y+1]= self.gp[y+1]| self.gp[x+1]
            self.p[x] = y # x の親を y にする
            return True
        else:
            return False

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


n,m = map(int,input().split())
p = [0] + list(map(int,input().split()))

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

parent = set()
for i in range(n):
    parent.add(uf.find(i))
ans = 0
for i in parent:
    ans += len(uf.g[i+1]) + len(uf.gp[i+1]) - len(uf.g[i+1] | uf.gp[i+1])
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

    def allset(self):
        d = defaultdict(set)
        for i in range(self.n):
            d[self.find(i)].add(i)
        for i in d.keys():
            d[i] = deque(list(d[i]))
        return d

def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    p = list(map(lambda x: x-1,p))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    d = uf.allset()
    for i in range(N):
        tmp = p[i]
        r = uf.find(tmp)
        if not uf.same(r,i):continue
        else:
            pre = p[i]
            if i in d[r]:
                new = i
                #d[r].remove(i)
            else:
                new = d[r].popleft()
            swap = p.index(new)
            p[i] = new
            p[swap] = pre
    for i in range(N):
        if p[i] != i: continue
        else:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

    def allset(self):
        d = defaultdict(set)
        for i in range(self.n):
            d[self.find(i)].add(i)
        for i in d.keys():
            d[i] = deque(sorted(list(d[i])))
        return d

def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    p = list(map(lambda x: x-1,p))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    d = uf.allset()
    for i in range(N):
        tmp = p[i]
        r = uf.find(tmp)
        if uf.same(r,i):
            pre = p[i]
            if i in d[r]:
                new = i
                #d[r].remove(i)
            else:
                new = d[r].popleft()
            swap = p.index(new)
            p[i] = new
            p[swap] = pre
    for i in range(N):
        if p[i] == i:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

    def allset(self):
        d = defaultdict(list)
        for i in range(self.n):
            d[self.find(i)] += [i]
        for i in d.keys():
            d[i].sort()
            d[i] = deque(d[i])
        return d

def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    p = list(map(lambda x: x-1,p))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    d = uf.allset()
    for i in range(N):
        tmp = p[i]
        r = uf.find(tmp)
        if uf.same(r,i):
            pre = p[i]
            if i in d[r]:
                new = i
                #d[r].remove(i)
            else:
                new = d[r].popleft()
            swap = p.index(new)
            p[i] = new
            p[swap] = pre
    for i in range(N):
        if p[i] == i:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

    def allset(self):
        d = defaultdict(list)
        for i in range(self.n):
            d[self.find(i)] += [i]
        t = list(d.keys())
        for i in t:
            d[i].sort()
            d[i] = deque(d[i])
        return d

def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    d = uf.allset()
    for i in range(N):
        p[i] -= 1
    for i in range(N):
        tmp = p[i]
        r = uf.find(tmp)
        if uf.same(r,i):
            pre = int(p[i])
            if i in d[r]:
                new = i
                #d[r].remove(i)
            else:
                new = d[r].popleft()
            swap = p.index(new)
            p[i] = new
            p[swap] = pre
    for i in range(N):
        if p[i] == i:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
from sys import stdin
from collections import defaultdict,deque
class UnionFind:
    def __init__(self,n):
        self.parent = [i for i in range(n)]
        self.rank = [0]*n
        self.n = n
    def find(self,x):
        if self.parent[x] == x:
            return x
        else:
            self.parent[x] = self.find(self.parent[x])
            return self.parent[x]
    def union(self,x,y):
        x = self.find(x)
        y = self.find(y)
        if x == y:return
        if self.rank[x] < self.rank[y]:
            self.parent[x] = y
        else:
            self.parent[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def same(self,x,y):
        return bool(self.find(x)==self.find(y))

    def allset(self):
        d = defaultdict(list)
        for i in range(self.n):
            d[self.find(i)] += [i]
        t = list(d.keys())
        for i in t:
            d[i].sort()
            d[i] = deque(d[i])
        return d

def main():
    N,M = map(int,stdin.readline().split())
    uf = UnionFind(N)
    p = list(map(int,stdin.readline().split()))
    ans = 0
    for _ in range(M):
        x,y = map(int,stdin.readline().split())
        x -= 1
        y -= 1
        uf.union(x,y)
    d = uf.allset()
    for i in range(N):
        p[i] -= 1
    for i in range(N):
        tmp = p[i]
        r = uf.find(tmp)
        if uf.same(r,i):
            pre = int(p[i])
            if i in d[r]:
                new = i
                d[r].remove(i)
            else:
                new = d[r].popleft()
            swap = p.index(new)
            p[i] = new
            p[swap] = pre
    for i in range(N):
        if p[i] == i:ans += 1
    print(ans)
    #print(*list(map(lambda x:x+1,p)))
if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

Solution code:
class unionFind:
    def __init__(self, n, p):
        p = [0] + p + [0]*9
        self.data = [-1] * (n+10)
        self.sets = [set([i]) for i in range(n+10)]
        self.valsets = [set([p[i]])for i in range(n+10)]

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

    def unite(self, x, y):
        a, b = self.find(x), self.find(y)
        if a!=b:
            self.sets[b] |= self.sets[a]
            self.valsets[b] |= self.valsets[a]
            self.data[b] += self.data[a]
            self.data[a] = b


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

tree = unionFind(n, p)
for i in range(m):
    x, y = map(int, input().split())
    tree.unite(x, y)

ans = -1
for i in range(n+1):
    if tree.data[i]<0:
        ans += len(tree.sets[i] & tree.valsets[i])
print(ans)