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:
from collections import defaultdict

def get_p(ind):
    global parent
    while parent[ind] != ind:
        ind = parent[ind]
    return ind

def get_p2(ind):
    global parent
    if parent[ind] != ind:
        parent[ind] = get_p2(parent[ind])
    return parent[ind]

parent = []

def main():
    global parent

    num, swap = map(int, input().split())
    data = list(map(int, input().split()))

    parent = [i for i in range(num + 1)]

    for i in range(swap):
        a, b = map(int, input().split())
        a_parent = get_p2(a)
        b_parent = get_p2(b)

        if a_parent != b_parent:
            parent[max(a_parent, b_parent)] = min(a_parent, b_parent)


    ans = 0


    for i in range(num):
        now_int = i + 1
        ind = data.index(i + 1)
        ind += 1
        if get_p(now_int) == get_p(ind):
            ans += 1
        elif ind == now_int:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict

def get_p(ind):
    global parent
    while parent[ind] != ind:
        ind = parent[ind]
    return ind

def get_p2(ind):
    global parent
    if parent[ind] != ind:
        parent[ind] = get_p2(parent[ind])
    return parent[ind]

parent = []

def main():
    global parent

    num, swap = map(int, input().split())
    data = list(map(int, input().split()))

    parent = [i for i in range(num + 1)]

    for i in range(swap):
        a, b = map(int, input().split())
        if parent[a] == a and parent[b] == b:
            parent[max(a, b)] = min(a, b)
        elif parent[a] != a and parent[b] != b:
            a_parent = get_p2(a)
            b_parent = get_p2(b)
            parent[max(a_parent, b_parent)] = min(a_parent, b_parent)
        elif parent[a] == a:
            parent[a] = get_p2(b)
        else:
            parent[b] = get_p2(a)

    ans = 0


    for i in range(num):
        now_int = i + 1
        ind = data.index(i + 1)
        ind += 1
        if get_p(now_int) == get_p(ind):
            ans += 1
        elif ind == now_int:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict

def get_p(ind, parent):
    while parent[ind] != ind:
        ind = parent[ind]
    return ind

def get_p2(ind, parent):
    while parent[ind] != -1:
        ind = parent[ind]
    return ind


def main():
    num, swap = map(int, input().split())
    data = list(map(int, input().split()))

    parent = [-1 for i in range(num + 1)]

    for i in range(swap):
        a, b = map(int, input().split())
        if parent[a] == -1 and parent[b] == -1:
            parent[max(a, b)] = min(a, b)
        elif parent[a] != -1 and parent[b] != -1:
            a_parent = get_p2(a, parent)
            b_parent = get_p2(b, parent)
            parent[max(a_parent, b_parent)] = min(a_parent, b_parent)
        elif parent[a] == -1:
            parent[a] = get_p2(b, parent)
        else:
            parent[b] = get_p2(a, parent)


    ans = 0

    for i in range(num + 1):
        if parent[i] == -1:
            parent[i] = i


    for i in range(num):
        now_int = i + 1
        ind = data.index(i + 1)
        ind += 1
        if get_p(now_int, parent) == get_p(ind, parent):
            ans += 1
        elif ind == now_int:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:

from collections import defaultdict

def get_p(ind, parent):
    while parent[ind] != ind:
        ind = parent[ind]
    return ind

def get_p2(ind, parent):
    while parent[ind] != -1:
        ind = parent[ind]
    return ind


def main():
    num, swap = map(int, input().split())
    data = list(map(int, input().split()))

    parent = [-1 for i in range(num + 1)]

    for i in range(swap):
        a, b = map(int, input().split())
        if parent[a] == -1 and parent[b] == -1:
            parent[max(a, b)] = min(a, b)
        elif parent[a] != -1 and parent[b] != -1:
            a_parent = get_p2(a, parent)
            b_parent = get_p2(b, parent)
            parent[max(a_parent, b_parent)] = min(a_parent, b_parent)
        elif parent[a] == -1:
            parent[a] = parent[b]
        else:
            parent[b] = parent[a]


    ans = 0

    for i in range(num + 1):
        if parent[i] == -1:
            parent[i] = i


    for i in range(num):
        now_int = i + 1
        ind = data.index(i + 1)
        ind += 1
        if get_p(now_int, parent) == get_p(ind, parent):
            ans += 1
        elif ind == now_int:
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
###############################################################################

from sys import stdout
from bisect import bisect_left as binl
from copy import copy, deepcopy
from collections import defaultdict


mod = 1


def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * y) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def combination(x, y):
    assert(x >= y)

    if y > x // 2:
        y = x - y

    ret = 1

    for i in range(0, y):
        j = x - i
        i = i + 1

        ret = ret * j
        ret = ret // i

    return ret


def get_divisors(x):
    retlist = []
    for i in range(1, int(x**0.5) + 3):
        if x % i == 0:
            retlist.append(i)
            retlist.append(x // i)
    return retlist


def get_factors(x):
    retlist = []
    for i in range(2, int(x**0.5) + 3):
        while x % i == 0:
            retlist.append(i)
            x = x // i
    retlist.append(x)
    return retlist


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


class UnionFind:

    def __init__(self, n):
        self.parent = [i for i in range(n)]

    def root(self, i):
        if (self.parent[i] == i):
            return i
        self.parent[i] = self.root(self.parent[i])
        return self.parent[i]

    def unite(self, i, j):
        rooti = self.root(i)
        rootj = self.root(j)
        if rooti == rootj:
            return
        if i < j:
            self.parent[rootj] = rooti
        else:
            self.parent[rooti] = rootj

    def same(self, i, j):
        return self.root(i) == self.root(j)


###############################################################################


def main():
    n, m = intin()
    plist = intina()
    xylist = intinl(m)

    new_xylist = []
    for x, y in xylist:
        if x < y:
            new_xylist.append((x, y))
            continue
        new_xylist.append((y, x))
    new_xylist.sort()
    xylist = new_xylist

    u = UnionFind(n)

    for x, y in xylist:
        u.unite(x - 1, y - 1)

    ans = 0

    for i, p in enumerate(plist):
        if u.same(i, p - 1):
            ans += 1

    print(ans)


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ [int(it)-1 for it in input().split()] for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

for a,b in sli:
  if ( b == ue[a] or a == ue[b] ):
    continue
  else:
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if (_a == _b and _a != -1):
      continue
      
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a

s = 0
for i in range(N):
  if ue[i]==-1:
    ue[i]=i 
for i in range(N):
  if (ue[i]==ue[pli[i]]):
    s+=1
print (s)

Submission status: Time Limit Exceeded

Solution code:
N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ (lambda a,b:[min(a,b),max(a,b)])(*[int(it)-1 for it in input().split()]) for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

for a,b in sli:
  if ( b == ue[a] or a == ue[b] ):
    continue
  else:
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if (_a == _b and _a != -1):
      continue
      
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a

s = 0
for i in range(N):
  if ue[i]==-1:
    ue[i]=i 
for i in range(N):
  if (ue[i]==ue[pli[i]]):
    s+=1
print (s)

Submission status: Time Limit Exceeded

Solution code:
N,M = [int(it) for it in input().split()]
pli=[int(it)-1 for it in input().split()]
sli=[ (lambda a,b:[min(a,b),max(a,b)])(*[int(it)-1 for it in input().split()]) for i in range(M)]
ue = [-1]*N
dw = [[] for i in range(N)]

#print (N,M,pli,sli)
#print (ue)
#print (dw)
for a,b in sli:
  if ( b == ue[a] or a == ue[b] ):
    continue
  if (1==1):
    _a = ue[a] if ue[a]!=-1 else a 
    _b = ue[b] if ue[b]!=-1 else b
    if (_a == _b and _a != -1):
      continue

    assert( ue[_a]==-1 )
    assert( ue[_b]==-1 )
      
    if len(dw[_b])>0:
      dw[_a].extend(dw[_b])
      for _p in dw[_b]:
        ue[_p]=_a
      dw[_b]=[]
    dw[_a].append(_b)
    ue[_b]=_a

s = 0
for i in range(N):
  if ue[i]==-1:
    ue[i]=i 
for i in range(N):
  if (ue[i]==ue[pli[i]]):
    s+=1
print (s)

Submission status: Time Limit Exceeded

Solution code:
N,M =map(int,input().split())
p = list(map(lambda x:int(x)-1,input().split()))
xy = [list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
group = [i for i in range(N)]
glist = [[i] for i in range(N)]
def merge(x,y):
    gx = group[x]
    gy = group[y]
    if gx == gy:
        return
    for y in glist[gy]:
        group[y] = gx
    glist[gx] += glist[gy]
    glist[gy] = []
    return
for x,y in xy:
    merge(x,y)
out = sum([len(set(row) & set(p[g] for g in row)) for row in glist])
print(out)

Submission status: Time Limit Exceeded

Solution code:
N,M =map(int,input().split())
p = list(map(lambda x:int(x)-1,input().split()))
xy = [list(map(lambda x:int(x)-1,input().split())) for _ in range(M)]
group = [i for i in range(N)]
glist = [[i] for i in range(N)]
def merge(x,y):
    gx = group[x]
    gy = group[y]
    if gx == gy:
        return
    for y in glist[gy]:
        group[y] = gx
    glist[gx] += glist[gy]
    glist[gy] = []
    return
for x,y in xy:
    merge(x,y)
out = 0
for row in glist:
    s_i = set()
    s_g = set()
    for g in row:
        s_i.add(g)
        s_g.add(p[g])
    out += len(s_i & s_g)
print(out)

Submission status: Time Limit Exceeded

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

def root(x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf[x])
        return uf[x]

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

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,readline().split())
p = list(map(int,readline().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,readline().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
N += 1
match = [[] for i in range(N)]
for i in range(1, N):
    match[uf[i]].append(i)
for i in range(1, N):
    matchlen = len(match[i])
    for j in range(matchlen):
        if p[match[i][j]] in match[i]:
            ans += 1
print(str(ans))

Submission status: Time Limit Exceeded

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

def root(x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf[x])
        return uf[x]

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

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,readline().split())
p = list(map(int,readline().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,readline().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
match = [[] for i in range(N+1)]
for i in range(1, N+1):
    match[uf[i]].append(i)
for i in range(1, N+1):
    matchlen = len(match[i])
    for j in range(matchlen):
        if p[match[i][j]] in match[i]:
            ans += 1
print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
def root(x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf[x])
        return uf[x]

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

def unite(x, y):
    rx = root(x)
    ry = root(y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,input().split())
p = list(map(int,input().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,input().split()))
    unite(a, b)
for i in range(1, N+1):
    root(i)

ans = 0
match = [[] for i in range(N+1)]
for i in range(1, N+1):
    match[uf[i]].append(i)
for i in range(1, N+1):
    matchlen = len(match[i])
    for j in range(matchlen):
        if p[match[i][j]] in match[i]:
            ans += 1
print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
def root(uf, x):
    if uf[x] == x:
        return x
    else:
        uf[x] = root(uf, uf[x])
        return uf[x]

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

def unite(uf, x, y):
    rx = root(uf, x)
    ry = root(uf, y)
    if rx == ry:
        return
    uf[rx] = ry

N, M = map(int,input().split())
p = list(map(int,input().split()))
p.insert(0, -1)
uf = [i for i in range(N+1)]
for i in range(M):
    a, b = (map(int,input().split()))
    unite(uf, a, b)
for i in range(1, N+1):
    root(uf, i)

ans = 0
match = [[] for i in range(N+1)]
for i in range(1, N+1):
    match[uf[i]].append(i)
for i in range(1, N+1):
    matchlen = len(match[i])
    for j in range(matchlen):
        if p[match[i][j]] in match[i]:
            ans += 1
print(str(ans))

Submission status: Time Limit Exceeded

Solution code:
import sys
 
n, m = [int(i) for i in input().split(" ")]
p = [0] + [int(i) for i in input().split(" ")]
par = [i for i in range(0, n + 1)]
id_set = [[i] for i in range(0, n + 1)]
p_set = [[p[i]] for i in range(0, n + 1)]

sys.setrecursionlimit(10**6)
 
def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        par[x] = r
        return r

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    else:
        par[x] = y
        id_set[y] = id_set[x] + id_set[y]
        p_set[y] = p_set[x] + p_set[y]

for i in range(0, m):
    x, y = [int(i) for i in input().split(" ")]
    unite(x, y)
    
s = 0
for i in range(1, n + 1):
    if i == root(i):
        id_i = sorted(id_set[i])
        p_i = sorted(p_set[i])
        k = 0
        for j in range(0, len(id_i)):
            while k < len(p_i) and p_i[k] < id_i[j]:
                k += 1
            if k >= len(p_i):
                break
            if p_i[k] == id_i[j]:
                s += 1

print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
n, m = [int(i) for i in input().split(" ")]
p = [0] + [int(i) for i in input().split(" ")]
par = [i for i in range(0, n + 1)]
id_set = [[i] for i in range(0, n + 1)]
p_set = [[p[i]] for i in range(0, n + 1)]

sys.setrecursionlimit(10**6)
 
def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        par[x] = r
        return r

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    else:
        par[x] = y
        id_set[y] = id_set[x] + id_set[y]
        p_set[y] = p_set[x] + p_set[y]

for i in range(0, m):
    x, y = [int(i) for i in input().split(" ")]
    unite(x, y)
    
s = 0
for i in range(1, n + 1):
    if i == root(i):
        s += len(set(id_set[i]) & set(p_set[i]))

print(s)

Submission status: Time Limit Exceeded

Solution code:
import sys
 
n, m = [int(i) for i in input().split(" ")]
p = [0] + [int(i) for i in input().split(" ")]
par = [i for i in range(0, n + 1)]
id_set = [{i} for i in range(0, n + 1)]
p_set = [{p[i]} for i in range(0, n + 1)]

sys.setrecursionlimit(10**6)
 
def root(x):
    if par[x] == x:
        return x
    else:
        r = root(par[x])
        par[x] = r
        return r

def unite(x, y):
    x = root(x)
    y = root(y)
    if x == y:
        return
    else:
        par[x] = y
        id_set[y] = id_set[x] | id_set[y]
        p_set[y] = p_set[x] | p_set[y]

for i in range(0, m):
    x, y = [int(i) for i in input().split(" ")]
    unite(x, y)
    
s = 0
for i in range(1, n + 1):
    if i == root(i):
        s += len(id_set[i] & p_set[i])

print(s)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
p=list(map(int,input().split()))
p=[0]+p

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

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

def union(x,y):
    if size[x]>size[y]:
        size[x]+=size[y]
        par[y]=find(x)
    elif size[y]>size[x]:
        size[y]+=size[x]
        par[x]=find(y)
    elif size[x]==size[y]:
        size[x]+=size[y]
        par[y]=find(x)
        
for i in range(M):
    a,b=map(int,input().split())
    if find(a)==find(b):
        pass
    else:
        union(find(a),find(b))
#print(par)
ans=0
for i in range(1,N+1):
    if find(i)==find(p.index(i)):
        ans+=1
        #print(i,find(i))
print(ans)

Submission status: Time Limit Exceeded

Solution code:
class Unionfind():
    def __init__(self, size):
        self.table = [-1 for _ in range(size)]
    def find(self, x):
        while(self.table[x] >= 0):
            x = self.table[x]
        return x
    def union(self, x, y):
        xl = self.find(x)
        yl = self.find(y)
        if xl != yl:
            if self.table[xl] <= self.table[yl]:
                self.table[yl] = xl
                self.table[xl] -= 1
            else:
                self.table[xl] = yl
                self.table[yl] -= 1
n, m = map(int, input().split())
p = list(map(int, input().split()))
edges = [tuple(map(int, input().split())) for _ in range(m)]
place = Unionfind(n)
d = {}
for x, y in edges:
    place.union(x-1, y-1)
loot = [0] * n
for i in range(n):
    loot[i] = place.find(i)
    if loot[i] not in d:
        d[loot[i]] = [p[i]-1]
    else:
        d[loot[i]].append(p[i]-1)
counter = 0
for i in range(n):
    if i in d[loot[i]]:
        counter += 1
print(counter)

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
p = list(map(int, input().split()))
swappair= [list(map(int, input().split())) for _ in range(M)]

union_list = [-1 for _ in range(N+1)]

def find(a): # get root
    while not union_list[a] == -1:
        a = union_list[a]
    return a

def merge(a,b): 
    ia = find(a)
    ib = find(b)
    if ia < ib:
        union_list[ib] = ia
    elif ia > ib:
        union_list[ia] = ib
    elif ia==ib:
        union_list[ia] -= 1
        union_list[ib] = ia
    


def is_same_grp(a,b):
    ia = find(a)
    ib = find(b)
    return ia == ib

for i in range(M):
    merge(*swappair[i])

ans = 0
for i in range(1,N+1):
    ans += int( is_same_grp(i, p[i-1]))

print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/mnt/c/Users/moiki/bash/env/bin/python
N,M = map(int, input().split())
p = list(map(int, input().split()))
swappair= [list(map(int, input().split())) for _ in range(M)]

union_list = [-1 for _ in range(N+1)]

def find(a): # get root
    while not union_list[a] == -1:
        a = union_list[a]
    return a

def merge(a,b): 
    ia = find(a)
    ib = find(b)
    union_list[ib] = ia

def is_same_grp(a,b):
    ia = find(a)
    ib = find(b)
    return ia == ib

for i in range(M):
    merge(*swappair[i])

ans = 0
for i in range(1,N+1):
    ans += int( is_same_grp(i, p[i-1]))

print(ans)

Submission status: Time Limit Exceeded

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

def dfs(x):
    if uf[x] == x:
        return x
    return dfs(uf[x])

for _ in range(m):
    xy = list(map(int, input().split()))
    rx, ry = dfs(xy[0]), dfs(xy[1])
    if rx != ry:
        uf[rx] = ry
count = 0
for i in range(n):
    num = i + 1
    if p[i] == num or dfs(num) == dfs(p[i]):
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())
p = list(map(int, input().split()))
xys = [list(map(int, input().split())) for _ in range(m)]
lsxy = {}
stxy = {}
maxi = 0
allst = set()
for xy in xys:
    xin = True if xy[0] in lsxy else False
    yin = True if xy[1] in lsxy else False
    allst.add(xy[0])
    allst.add(xy[1])
    if xin and yin:
        xidx = lsxy[xy[0]]
        yidx = lsxy[xy[1]]
        stx = stxy[xidx]
        sty = stxy[yidx]
        if len(stx) > len(sty):
            stxy[xidx] |= stxy.pop(yidx)
            for i in sty:
                lsxy[i] = xidx
        else:
            stxy[yidx] |= stxy.pop(xidx)
            for i in stx:
                lsxy[i] = yidx
    elif xin:
        lsxy[xy[1]] = lsxy[xy[0]]
        stxy[lsxy[xy[0]]].add(xy[1])
    elif yin:
        lsxy[xy[0]] = lsxy[xy[1]]
        stxy[lsxy[xy[1]]].add(xy[0])
    else:
        stxy[maxi] = set(xy)
        lsxy[xy[0]] = maxi
        lsxy[xy[1]] = maxi
        maxi += 1
count = 0
for i in range(n):
    if i + 1 == p[i]:
        count += 1
    elif i + 1 in lsxy and p[i] in stxy[lsxy[i + 1]]:
        count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
n,m = map(int,input().split())
p = list(map(int,input().split()))
info = [list(map(int,input().split())) for _ in range(m)]

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

# xの根を見つける
def root(x):
  if par[x] == x:
    return x
  else:
    par[x] = root(par[x])
    return par[x]
  
# x,yの根が同じかどうかを返す（根が同じ:True、根が異なる:False）
def find(x, y):
  return root(x) == root(y)

# xとyの根を結合させる
def union(x, y):
  x = root(x)
  y = root(y)
  if rank[x] < rank[y]:
    par[x] = y
  else:
    par[y] = x
    if rank[x] == rank[y]:
      rank[x] += 1

for i in range(m):
  union(info[i][0],info[i][1])

ans = 0

for i in range(n):
  if find(i+1,p.index(i+1)+1):
    ans += 1
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
from collections import deque
from pprint import pprint
N, M = map(int, input().split())
p = list(map(int, input().split()))
xy = [list(map(int, input().split())) for _ in range(M)]

graph = [[0 for _ in range(N)] for _ in range(N)]
visited = [0 for _ in range(N)]

for x,y in xy:
    graph[x-1][y-1] = 1
    graph[y-1][x-1] = 1

def dfs(v):
    que = deque()
    vis_list = []
    visited[v] = 1
    vis_list.append(v)
    que.append(v)
    while len(que) > 0:
        i = que.pop()   #深さ優先探索
        # i = que.popleft() #幅優先探索
        for n in range(N):
            if graph[i][n] == 1 and visited[n] == 0:
                visited[n] = 1
                vis_list.append(n)
                que.append(n)

    return vis_list

grps = []
for i in range(N):
    if visited[i] == 0:
        grps.append(dfs(i))

ans = 0
for g_list in grps:

    if len(g_list) == 1:
        if g_list[0] == p[g_list[0]]-1:
            ans += 1
    else:
        tmp = set([])
        for i in g_list:
            tmp.add(p[i]-1)
        ans += len( set(g_list) & tmp)

print(ans)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
P_list=[int(p) for p in input().split()]
Tree=[-1]*N
def find(x):
  while Tree[x]>=0:
    x=Tree[x]
  return x
def unite(x,y):
  s1=find(x)
  s2=find(y)
  if s1==s2:
    pass
  else:
    if Tree[s1]<Tree[s2]:
      Tree[s2]=s1
    elif Tree[s2]>Tree[s1]:
      Tree[s1]=s2
    else:
      Tree[s1]+=-1
      Tree[s2]=s1
  return
for m in range(M):
  x,y=map(int,input().split())
  unite(x-1,y-1)
ans=0
for i in range(N):
  if find(P_list[i]-1)==find(i):
    ans+=1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
paths = {}
for _ in range(m):
    x, y = map(int, input().split())
    if not x in paths.keys():
        paths[x] = [y]
    else:
        paths[x].append(y)
    if not y in paths.keys():
        paths[y] = [x]
    else:
        paths[y].append(x)

connected = [None]*(n+1)
path_id = 1
for i in range(1, n+1):
    if connected[i] is None:
        connected[i] = path_id
    else:
        continue

    stack = deque(paths[i]) if i in paths.keys() else []
    while len(stack) > 0:
        j = stack.pop()
        connected[j] = path_id
        for k in paths[j]:
            if connected[k] is None and not k in stack:
                stack.append(k)
    path_id += 1
# print(connected)

ans = 0
for i in range(n):
    if connected[i+1] == connected[p[i]]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
paths = {}
for _ in range(m):
    x, y = map(int, input().split())
    if not x in paths.keys():
        paths[x] = [y]
    else:
        paths[x].append(y)
    if not y in paths.keys():
        paths[y] = [x]
    else:
        paths[y].append(x)

connected = [None]*(n+1)
path_id = 1
for i in range(1, n+1):
    if connected[i] is None:
        connected[i] = path_id
    else:
        continue

    stack = deque(paths[i]) if i in paths.keys() else []
    while len(stack) > 0:
        j = stack.pop()
        connected[j] = path_id
        for k in paths[j]:
            if connected[k] is None:
                stack.append(k)
    path_id += 1
# print(connected)

ans = 0
for i in range(n):
    if connected[i+1] == connected[p[i]]:
        ans += 1
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
n, m = map(int, input().split())
p = list(map(int, input().split()))
paths = {}
for _ in range(m):
    x, y = map(int, input().split())
    if not x in paths.keys():
        paths[x] = [y]
    else:
        paths[x].append(y)
    if not y in paths.keys():
        paths[y] = [x]
    else:
        paths[y].append(x)

connected = [None]*(n+1)
path_id = 1
for i in range(1, n+1):
    if connected[i] is None:
        connected[i] = path_id
    else:
        continue
    que = deque(paths[i]) if i in paths.keys() else []
    while len(que) > 0:
        j = que.popleft()
        connected[j] = path_id
        for k in paths[j]:
            if connected[k] is None:
                que.append(k)
    path_id += 1
# print(connected)

ans = 0
for i in range(n):
    if connected[i+1] == connected[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(" ")))
xy = []
for i in range(M):
    aa = input().split(" ")
    x = int(aa[0])
    y = int(aa[1])
    xy.append([x,y])
link = []
linklist = []
for i in range(M):
    x = xy[i][0]
    y = xy[i][1]
    if (x not in linklist)and(y not in linklist):
        #一度も出現していないので新たなに枝を作成
        linklist.append(x)
        linklist.append(y)
        link.append(xy[i])
    elif (x in linklist)and(y in linklist):
        #枝と枝を結ぶ
        for j in range(len(link)):
            if x in link[j]:
                Xnode = link[j]
                break
        for j in range(len(link)):
            if y in link[j]:
                Ynode = link[j]
                break
        if Xnode == Ynode:
            continue
        else:
            new = Xnode+Ynode
            link.append(new)
            link.remove(Xnode)
            link.remove(Ynode)
    else:
        #枝を広げる
        for j in range(len(link)):
            if x in link[j]:
                link[j].append(y)
                linklist.append(y)
                break
            if y in link[j]:
                link[j].append(x)
                linklist.append(x)
                break
count = 0
for i in range(len(p)):
    if p[i] == (i+1):
        count += 1
    elif p[i] not in linklist:
        continue
    else:
        for j in range(len(link)):
            if (p[i] in link[j])and((i+1) in link[j]):
                count += 1
print(count)

Submission status: Time Limit Exceeded

Solution code:
N, M = map( int, input().split())
P = list( map( int, input().split()))
par = [ i for i in range(N)]

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

for i in range(M):
    x, y = map( int, input().split())
    x, y = x-1, y-1
    bx, by = find(x), find(y)
    par[y] = bx
    par[by] = bx

ans = 0
for i in range(N):
    if find(i) == find(P[i]-1):
        ans += 1
print(ans)