Problem:


Score : 400 points

Problem Statement

We have a permutation of the integers from 1 through N, p_1, p_2, .., p_N.
We also have M pairs of two integers between 1 and N (inclusive), represented as (x_1,y_1), (x_2,y_2), .., (x_M,y_M).
AtCoDeer the deer is going to perform the following operation on p as many times as desired so that the number of i (1 ≤ i ≤ N) such that p_i = i is maximized:

Choose j such that 1 ≤ j ≤ M, and swap p_{x_j} and p_{y_j}.

Find the maximum possible number of i such that p_i = i after operations.

Constraints

2 ≤ N ≤ 10^5

1 ≤ M ≤ 10^5

p is a permutation of integers from 1 through N.

1 ≤ x_j,y_j ≤ N

x_j ≠ y_j

If i ≠ j, \{x_i,y_i\} ≠ \{x_j,y_j\}.

All values in input are integers.

Input

Input is given from Standard Input in the following format:

N M
p_1 p_2 .. p_N
x_1 y_1
x_2 y_2
:
x_M y_M

Output

Print the maximum possible number of i such that p_i = i after operations.

Sample Input 1

5 2
5 3 1 4 2
1 3
5 4

Sample Output 1

2

If we perform the operation by choosing j=1, p becomes 1 3 5 4 2, which is optimal, so the answer is 2.

Sample Input 2

3 2
3 2 1
1 2
2 3

Sample Output 2

3

If we perform the operation by, for example, choosing j=1, j=2, j=1 in this order, p becomes 1 2 3, which is obviously optimal.
Note that we may choose the same j any number of times.

Sample Input 3

10 8
5 3 6 8 7 10 9 1 2 4
3 1
4 1
5 9
2 5
6 5
3 5
8 9
7 9

Sample Output 3

8

Sample Input 4

5 1
1 2 3 4 5
1 5

Sample Output 4

5

We do not have to perform the operation. 



Sample input:
5 2
5 3 1 4 2
1 3
5 4


Sample output:
2

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self, no):
        self.parent = None
        self.rank = 0
        self.size = 1
        self.no = no

    def getRoot(self):
        if self.parent is None:
            return self
        else:
            self.parent = self.parent.getRoot()
            return self.parent

    def getSize(self):
        return self.getRoot().size

    def union(self, x):
        r = self.getRoot()
        xr = x.getRoot()
        if xr.rank > r.rank:
            r.parent = xr
            xr.size += r.size
        elif xr.rank < r.rank:
            xr.parent = r
            r.size += xr.size
        elif xr != r:
            xr.parent = r
            r.rank += 1
            r.size += xr.size

N, M = map(int, input().split())
V = list(map(int, input().split()))
s = []
for i in range(N):
    s.append(DisjointSet(i+1))

for i in range(M):
    u, v = map(int, input().split())
    s[u-1].union(s[v-1])

dic = {}
for i in range(N):
    gid = s[i].getRoot().no
    if gid not in dic:
        A = set()
        B = set()
        dic[gid] = (A, B)
    else:
        A, B = dic[gid]
    A.add(i+1)
    B.add(V[i])
    # print(i+1, gid, V[i])

ans = 0
for key in dic.keys():
    aa = len(dic[key][0] & dic[key][1])
    # print(key, dic[key], aa)
    ans += aa

print(ans)

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)

    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1

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

n, m = map(int, input().split())
p = [int(x) for x in input().split()]

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

cnt = 0

for i in range(n):
    if uni.same_check(p[i], i + 1):
        cnt += 1
print(cnt)

Submission status: Accepted

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

par = [i for i in range(n)]
#rootの計算量は、parが最初の状態に近いほど値は小さくて、高々O(n)
def root(x):
	tmp = par[x]
	if tmp == x:
		return x
	else:
		a = root(tmp)
		par[x] = a
		return a

def merge(x, y):
	x = root(x)
	y = root(y)
	if x != y:
		par[x] = y
		return

for i in range(m):
	x, y = map(int, input().split())
	merge(x-1, y-1)
	#print(par)

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(n+1)]
group = [0]*(n+1)
ans = 0
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += group[num] == group[i]
print(ans)

Submission status: Accepted

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

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


Swap=[None]*M
for i in range(M):
    Swap[i]=sorted(map(int,input().split()))

def find(x):
    while Group[x] != x:
        x=Group[x]
    return x

for i in range(M):
    if find(Swap[i][1]) != find(Swap[i][0]):
        Group[find(Swap[i][1])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[find(Swap[i][0])]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))
        Group[Swap[i][1]]=min(find(Swap[i][1]),find(Swap[i][0]))

count=0

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


print(count)

Submission status: Accepted

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

def root(x):
	tmp = par[x]
	if tmp == x:
		return x
	else:
		a = root(tmp)
		par[x] = a
		return a

def merge(x, y):
	x = root(x)
	y = root(y)
	if x != y:
		par[x] = y
		return

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

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
n,m = map(int, input().split())
p = list(map(int, input().split()))
par = [i for i in range(n)]
rank = [0 for x in range(n)]

def root(x):
	tmp = par[x]
	if tmp == x:
		return x
	else:
		a = root(tmp)
		par[x] = a
		return a

def merge(x, y):
	x = root(x)
	y = root(y)
	if x == y:
		return
	else:
		if rank[x] > rank[y]:
			par[y] = x
			rank[y] += rank[x]
		else:
			par[x] = y
			rank[x] += rank[y]
		return

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

ans = 0

for i in range(n):
	if p[i]-1 == i:
		ans += 1
	elif root(p[i]-1) == root(i):
		ans += 1

print(ans)

Submission status: Accepted

Solution code:
# coding: utf-8

class UnionFind:
    # 同一グループに入る番号について、根源の番号を記録するテーブルを初期化して作成する
    def __init__(self, size):
        # テーブルが負の値の場合、そのグループの根源となる番号で、負の値の大きさはメンバーの数
        # 正の値は所属するグループの根源の番号を指す
        self.table = [-1 for _ in range(size)]

    # グループの根源を探索する
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 同一グループとなる番号を辿り、大本の根源となる番号まで探索する
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 同一グループに属する場合、根源となる番号にまとめて管理する(大きなグループに併合する)
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            # 根源となる番号については、マイナス符号を付けてメンバー数を記録しているため、小さいほうが所属メンバーが多い
            if self.table[s1] <= self.table[s2]:
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2

            return True
        return False


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

s = UnionFind(N)

for i in range(M):
    a, b = map(int, input().split())
    s.union(a-1, b-1)

ans = 0
for i in range(N):
    # 初めから番号と位置が合っている場合
    if p[i] == i+1:
        ans += 1
    # 順列の番号と位置の番号が同一の根源になる場合、入れ替えが可能
    elif s.find(p[i]-1) == s.find(i):
        ans += 1

print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
class UnionFind:
  def __init__(self, n):
    self.table = [-1 for _ in range(n)]
    
  def root(self, x):
    if self.table[x] < 0:
      return x
    else:
      self.table[x] = self.root(self.table[x])
      return self.table[x]
  
  def unite(self, x, y):
    s1, s2 = self.root(x), self.root(y)
    if s1 != s2:
      if self.table[s1] != self.table[s2]:
        if self.table[s1] < self.table[s2]:
          self.table[s2] = s1
        else:
          self.table[s1] = s2
      else:
        self.table[s1] += -1
        self.table[s2] = s1
    return
  
  def findSet(self, x, y):
    return self.root(x) == self.root(y)
uf = UnionFind(N)
for i in range(M):
  px, py = map(int, input().split())
  px -= 1
  py -= 1
  uf.unite(px, py)
ans = 0
for i, v in enumerate(p):
  if uf.findSet(i,v):
    ans += 1
print(ans)

Submission status: Accepted

Solution code:

class UnionFind():
    def __init__(self, n):
        self.par = []
        for i in range(n+1):
            self.par.append(i)

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

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if(x == y) :
            return
        self.par[x] = y




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, y)


count = 0
for index in range(n):
    start = index + 1
    to = p[index]
    if uf.same(start, to):
        count += 1
print(count)

Submission status: Accepted

Solution code:
def solve():
  n, m = map(int,input().split())
  plst = list(map(int,input().split()))
  pare_inds = [i for i in range(n)]
  rank = [0 for i in range(n)]
  
  def find(x):
    p = pare_inds[x]
    if p == x:
      return x
    a = find(p)
    pare_inds[x] = a
    return a
  
  def unite(x, y):
    x = find(x)
    y = find(y)
    if x == y:
      return
    if rank[x] < rank[y]:
      pare_inds[x] = y
    else:
      pare_inds[y] = x
      if rank[x] == rank[y]:
        rank[x] += 1

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

  for i in range(m):
    x, y = map(int,input().split())
    x, y = x - 1, y - 1
    unite(x, y)
  
  ans = 0
  for i in range(n):
    if same(i, plst[i] - 1):
      ans += 1

  print(ans)
solve()

Submission status: Accepted

Solution code:
def solve():
  n, m = map(int,input().split())
  plst = list(map(int,input().split()))
  pare_inds = [i for i in range(n)]
  
  def find(x):
    p = pare_inds[x]
    if p == x:
      return x
    a = find(p)
    pare_inds[x] = a
    return a
  
  for i in range(m):
    x, y = map(int,input().split())
    x, y = x - 1, y - 1
    r_x, r_y  = find(x), find(y)
    pare_inds[y] = r_x
    pare_inds[r_y] = r_x
  
  ans = 0
  for i in range(n):
    if find(i) == find(plst[i] - 1):
      ans += 1

  print(ans)
solve()

Submission status: Accepted

Solution code:
N,M = list(map(int,input().strip().split(' ')))
P = list(map(int,input().strip().split(' ')))
X =[]
for i in range(M):
    X.append( list(map(int,input().strip().split(' '))))
    
    #initialize union-find tree
par = [i for i in range(1,N+1)]

def GetRoot(a):
    ind = a-1
    if par[ind]==a:
        return a
    else:
        par[ind] = GetRoot(par[ind])
        return par[ind]

def unite(a,b):
    aRoot,bRoot = GetRoot(a),GetRoot(b)
    if aRoot >= bRoot:
        par[aRoot-1] = bRoot
    else:
        par[bRoot-1] = aRoot
        
for j in X:
    unite(j[0],j[1])

result = 0
for p in P:
    if GetRoot(p) == GetRoot(P[p-1]):
        result = result+1
print(result)

Submission status: Accepted

Solution code:

class UnionFindSet:
    def __init__(self):
        self.dic = dict()

    def find(self,x):
        #xがedgeを持っているかどうかの判定
        if x not in self.dic:
            return x
        else:
            self.dic[x] = self.find(self.dic[x])
            return self.dic[x]

    def union(self,x,y):
        fx = self.find(x)
        fy = self.find(y)
        if fx != fy:
            self.dic[fx] = fy

n, m = map(int,input().split())
p = [None] + list(map(int,input().split()))
s = UnionFindSet()
#最小全域木の作成
for _ in range(m):
    x,y = map(int,input().split())
    s.union(x,y)

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

Submission status: Accepted

Solution code:
class UnionFind:
    def __init__(self, size):
        # 負の値はルート (集合の代表) で集合の個数
        # 正の値は次の要素を表す
        self.table = [-1 for _ in range(size)]

    # 集合の代表を求める
    def find(self, x):
        if self.table[x] < 0:
            return x
        else:
            # 経路の圧縮
            self.table[x] = self.find(self.table[x])
            return self.table[x]

    # 併合
    def union(self, x, y):
        s1 = self.find(x)
        s2 = self.find(y)
        if s1 != s2:
            if self.table[s1] <= self.table[s2]:
                # 小さいほうが個数が多い
                self.table[s1] += self.table[s2]
                self.table[s2] = s1
            else:
                self.table[s2] += self.table[s1]
                self.table[s1] = s2
            return True
        return False

    # 部分集合とその要素数を返す
    def subsetall(self):
        a = []
        for i in xrange(len(self.table)):
            if self.table[i] < 0:
                a.append((i, -self.table[i]))
        return a

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

s = UnionFind(N)

for i in range(M):
  a, b = map(int, input().split())
  s.union(a-1,b-1)

ans = 0
for i in range(N):
  if p[i] == i+1: ans +=1
  elif s.find(p[i]-1) == s.find(i): ans+=1
print(ans)

Submission status: Accepted

Solution code:
def main():
    """
    2 <= N <= 10^5
    1 <= M <= 10^5
    p: 順列

    1 <= xi, yi <= N
    xi != yj
    if i != j then {xi, yi} != {xj, yj}
    """
    N, M = map(int, input().split())
    *p, = map(int, input().split())
    xy = [
        list(map(int, input().split()))
        for _ in range(M)
    ]

    editorial(N, M, p, xy)


class UnionFind:
    def __init__(self, par):
        self.par = par

    def root(self, x):
        if self.par[x] == x:
            return x
        # 経路圧縮
        self.par[x] = self.root(self.par[x])
        return self.par[x]

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

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

        if x != y:
            self.par[y] = x


def editorial(N, M, p, xy):
    par = list(range(N+1))
    uf = UnionFind(par)
    for x, y in xy:
        uf.unite(x, y)

    _p = [0] + p
    ans = 0
    for i in range(1, N+1):
        if uf.root(i) == uf.root(_p[i]):
            ans += 1

    print(ans)


def f(N, M, p, xy):
    """
    (1, 2): 1,2を入れ替える
    (2, 3): 2,3を入れ替える
        default: 123
            1,2: 213
            2,3: 231
        defaultからの移動: (1,3), (1,2)
        (1,2),(2,3) -> (1,3),(1,2)
        入れ替えると2番目xが1番目xになる？

    入力例1より、j=1,2,1の順で入れ替え
        j1=(1,2),j2=(2,3) => (1,3)
    """
    d_xy = {x: y for x, y in xy}
    d_yx = {y: x for x, y in xy}
    extra = []
    for x, y in xy:
        if y in d_xy:
            extra.append((x, d_xy[y]))

    print(xy)
    print("---")
    print(extra)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFindSet:
    def __init__(self):
        self.dic = dict()

    def find(self, x):
        if x not in self.dic:
            return x
        else:
            self.dic[x] = self.find(self.dic[x])
            return self.dic[x]

    def union(self, x, y):
        fx = self.find(x)
        fy = self.find(y)
        if fx != fy:
            self.dic[fx] = fy

n, m = map(int, input().split())
p = [None] + list(map(int, input().split()))
s = UnionFindSet()
for _ in range(m):
    x, y = map(int, input().split())
    s.union(p[x], p[y])
ans =0
for i in range(n, 0, -1):
    if s.find(i) == s.find(p[i]):
        ans += 1
print(ans)

Submission status: Accepted

Solution code:
# UnionFindで参考にしたページ
# http://www.geocities.jp/m_hiroi/light/pyalgo61.html


# 集合の代表を求める
def find(x):
    if link[x] < 0:
        return x
    else:
        # 経路の圧縮
        link[x] = find(link[x])
        return link[x]


# 併合
def union(x, y):
    s1 = find(x)
    s2 = find(y)
    if s1 != s2:
        if link[s1] >= link[s2]:
            # 小さいほうが個数が多い
            link[s2] += link[s1]
            link[s1] = s2
        else:
            link[s1] += link[s2]
            link[s2] = s1
        return True
    return False


N, M = map(int, input().split())
p = list(map(int, input().split()))
link = [-1 for _ in range(N + 1)]

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

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

Submission status: Accepted

Solution code:
# UnionFindで参考にしたページ
# http://www.geocities.jp/m_hiroi/light/pyalgo61.html


# 集合の代表を求める
def find(x):
    if link[x] < 0:
        return x
    else:
        # 経路の圧縮
        link[x] = find(link[x])
        return link[x]


# 併合
def union(x, y):
    s1 = find(x)
    s2 = find(y)
    if s1 != s2:
        if link[s1] >= link[s2]:
            # 小さいほうが個数が多い
            link[s1] += link[s2]
            link[s2] = s1
        else:
            link[s2] += link[s1]
            link[s1] = s2
        return True
    return False


N, M = map(int, input().split())
p = list(map(int, input().split()))
link = [-1 for _ in range(N + 1)]

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

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

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(n+1)]
group = [0]*(n+1)
ans = 0
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += group[num] == group[i]
print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(n+1)]
group = [0]*(n+1)
ans = 0
for _ in range(m):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p,1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += group[num] == group[i]
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(N+1)]
group = [0]*(N+1)
ans = 0
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if not group[point]:
            group[point] = i
            space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = [int(i) for i in input().split()]
graph = [[] for _ in range(N+1)]
group = [0]*(N+1)
ans = 0
for _ in range(M):
    x, y = (int(i) for i in input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
p = [int(i) for i in input().split()]
# graph = [[]]*(N+1)
graph = [[] for _ in range(N+1)]
group = [0]*(N+1)
ans = 0
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
# p = [int(i) for i in input().split()]
p = map(int,input().split())
# graph = [[]]*(N+1)
graph = [[] for _ in range(N+1)]
group = [0]*(N+1)
ans = 0
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
for i, num in enumerate(p, 1):
    space = [i]
    for point in space:
        if group[point]:
            continue
        group[point] = i
        space.extend(graph[point])
    ans += (group[num] == group[i])
print(ans)

Submission status: Accepted

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

def root(val):
    if parent[val]==val:
        return val
    else:
        parent[val]=root(parent[val])
        return parent[val]

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

def unite(x,y):
    xr=root(x)
    yr=root(y)
    if xr==yr :return
    parent[xr]=yr
p=list(map(int, input().split()))
X=[]
Y=[]
for i in range(M):
    x,y=map(int, input().split())
    X.append(x)
    Y.append(y)
    unite(x-1,y-1)
ct=0
for i,pp in enumerate(p):
    ct+=same(i,pp-1)
print(ct)

Submission status: Accepted

Solution code:
n,m = (int(i) for i in input().split())
par,rank = [i for i in range(n+1)],[0 for i in range(n+1)]
def root(x):
	if par[x]!=x: par[x] = root(par[x])
	return par[x]
def unite(x,y):
	x2,y2 = root(x),root(y)
	if x2!=y2:
		if rank[x2]<rank[y2]: par[x2] = y2
		else: par[y2] = x2
		if rank[x2]==rank[y2]: rank[x2]+=1
p = [int(i) for i in input().split()]
x = [[int(i) for i in input().split()] for i in range(m)]
for i,j in x: unite(i,j)
ans = -1
for i,j in enumerate([0]+p):
	if root(i)==root(j): ans += 1
print(ans)

Submission status: Accepted

Solution code:
from collections import deque
# coding: UTF-8

n,m = map(int,input().split())
p = list(map(int,input().split()))
links = {}
checked = set()
for i in range(n):
    links[i] = set()
for i in range(m):
    x,y = map(int,input().split())
    v=x-1
    w=y-1
    links[v].add(w)
    links[w].add(v)
queue = deque()
ans = 0

for start in range(n):
    if start in checked:
        continue

    v = start
    queue.appendleft(v)
    checked.add(v)

    cluster = set()
    cluster.add(v)
    values = set()
    values.add(p[v]-1)

    while queue:
        v = queue.pop()
        neighbors = links[v]
        for w in neighbors:
            if w in checked:
                continue
            else:
                queue.appendleft(w)
                checked.add(w)
                cluster.add(w)
                values.add(p[w]-1)

    common = len (cluster & values)
    ans += common

print(ans)

Submission status: Accepted

Solution code:
def solve():
  n, m = map(int,input().split())
  plst = list(map(int,input().split()))
  pare_inds = [i for i in range(n)]
  belongs = [[] for i in range(n)]
  
  def get_root(x):
    p = pare_inds[x]
    if p == x:
      return x
    a = get_root(p)
    pare_inds[x] = a
    return a
  
  for i in range(m):
    x, y = map(int,input().split())
    x, y = x - 1, y - 1
    r_x, r_y  = get_root(x), get_root(y)
    if r_x < r_y:
      pare_inds[y] = r_x
      pare_inds[r_y] = r_x
    else:
      pare_inds[x] = r_y
      pare_inds[r_x] = r_y
  
  for i in range(n):
    belongs[get_root(i)].append(i)

  ans = 0

  for lst in belongs:
    lst2 = [plst[i] - 1 for i in lst]
    set1 = set(lst)
    set2 = set(lst2)
    ans += len(set1 & set2)
#    lst.sort()
#    lst2.sort()
#    ind1 = 0
#    ind2 = 0
#    end = len(lst)
#    while ind1 < end and ind2 < end:
#      if lst[ind1] == lst2[ind2]:
#        ans += 1
#        ind1 += 1
#        ind2 += 1
#      elif lst[ind1] < lst2[ind2]:
#        ind1 += 1
#      else:
#        ind2 += 1
  
  print(ans)
solve()

Submission status: Accepted

Solution code:
def solve():
  n, m = map(int,input().split())
  plst = list(map(int,input().split()))
  pare_inds = [i for i in range(n)]
  belongs = [[] for i in range(n)]
  
  def get_root(x):
    p = pare_inds[x]
    if p == x:
      return x
    a = get_root(p)
    pare_inds[x] = a
    return a
  
  for i in range(m):
    x, y = map(int,input().split())
    x, y = x - 1, y - 1
    r_x, r_y  = get_root(x), get_root(y)
    if r_x < r_y:
      pare_inds[y] = r_x
      pare_inds[r_y] = r_x
    else:
      pare_inds[x] = r_y
      pare_inds[r_x] = r_y
  
  for i in range(n):
    belongs[get_root(i)].append(i)
  #print(belongs)
  #print(plst)
  ans = 0
  for lst in belongs:
    lst2 = [plst[i] - 1 for i in lst]
    lst.sort()
    lst2.sort()
    ind1 = 0
    ind2 = 0
    end = len(lst)
    while ind1 < end and ind2 < end:
      if lst[ind1] == lst2[ind2]:
        ans += 1
        ind1 += 1
        ind2 += 1
      elif lst[ind1] < lst2[ind2]:
        ind1 += 1
      else:
        ind2 += 1
  
  print(ans)
solve()

Submission status: Accepted

Solution code:
class DisjointSet:
    def __init__(self):
        self.rank = {}
        self.p = {}

    def makeSet(self, x):
        self.p[x] = x
        self.rank[x] = 0

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

    def unite(self, x, y):
        self.link(self.findSet(x), self.findSet(y))

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

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

n, m = map(int, input().split())
p = [int(v) for v in input().split()]

ds = DisjointSet()

for pi in p:
    ds.makeSet(pi)

for i in range(m):
    x,y = map(int, input().split())
    ds.unite(p[x-1], p[y-1])

ans = 0
for i,pi in enumerate(p):
    if ds.same(pi, i+1):
        ans += 1

print(ans)

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def check(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(N)

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

Ans = 0
for i,p in enumerate(P,1):
    Ans += 1 if uf.check(i,p) else 0

print(Ans)

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
p = [-1] + map(int, raw_input().split())
parent = {i: i for i in range(1, n+1)}
def root(x):
    if parent[x] != x:
        parent[x] = root(parent[x])
    return parent[x]
for i in range(m):
    x, y = map(int, raw_input().split())
    rx = root(x)
    ry = root(y)
    rx, ry = sorted([rx, ry])
    parent[x] = rx
    parent[y] = rx
    parent[ry] = rx

D = {} # root => (number set, order set)
for i in range(1, n+1):
    r = root(i)
    if not r in D:
        D[r] = (set(), set())
    D[r][0].add(i)
    D[r][1].add(p[i])
print sum([len(S & T) for S, T in D.values()])

Submission status: Accepted

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

class UnionFind:
    def __init__(self, n):
        self.par = [i for i in range(n+1)]
        self.rank = [0] * (n+1)
    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 self.rank[x] < self.rank[y]:
            self.par[x] = y
        else:
            self.par[y] = x
            if self.rank[x] == self.rank[y]:
                self.rank[x] += 1
    def check(self, x, y):
        return self.find(x) == self.find(y)

uf = UnionFind(N)

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

Ans = 0
for i,p in enumerate(P):
    Ans += 1 if uf.check(i,p) else 0

print(Ans)

Submission status: Accepted

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

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

def get_parent(x):
    if x == parent[x]:
        return x
    else:
        return get_parent(parent[x])

for _ in range(M):
    a, b = map(int, input().split())
    pa, pb = map(get_parent, [a,b])
    if pa == pb:
        continue
    if depth[pa] < depth[pb]:
        pa, pb = pb, pa
        a, b = b, a
    parent[pb] = pa
    depth[pa] = max(depth[pa], depth[pb]+1)


index = [[] for _ in range(N+1)]
value = [[] for _ in range(N+1)]
for n in range(1, N+1):
    p = get_parent(n)
    index[p].append(n)
    value[p].append(init[n-1])

ans = 0
for n in range(1, N+1):
    idx, val = index[n], value[n]
    if idx:
        idx.sort()
        val.sort()
        i, j = 0, 0
        while i < len(idx) and j < len(idx):
            if idx[i] == val[j]:
                ans += 1
                i += 1
                j += 1
            elif idx[i] > val[j]:
                j += 1
            else:
                i += 1
print(ans)

Submission status: Accepted

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

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

for i,num in enumerate(p,1):
    exploration_space = [i]
    for exploration_point in exploration_space:
        if group[exploration_point]:
            continue
        group[exploration_point] = i
        exploration_space.extend(graph[exploration_point])
    ans += (group[num] == group[i])

print(ans)

Submission status: Accepted

Solution code:
n, m = map(int, raw_input().split())
p = [-1] + map(int, raw_input().split())
edge = {i: [] for i in range(1, n+1)}
for i in range(m):
    x, y = map(int, raw_input().split())
    edge[x].append(y)
    edge[y].append(x)
ans = 0
used = [False] * (n+1)
for i in range(1, n+1):
    if used[i]:
        continue
    used[i] = True
    que = [i]
    S = set([i])
    T = set([p[i]])
    while que:
        u = que.pop(0)
        for v in edge[u]:
            if used[v]:
                continue
            que.append(v)
            used[v] = True
            S.add(v)
            T.add(p[v])
    ans += len(S & T)
print ans