222. 순열 사이클

백준

1. DFS

import sys
input = sys.stdin.readline

def dfs(start):
  visit[start] = True
  for i in graph[start]:
    if not visit[i]:
      dfs(i)

for t in range(int(input())):
  n = int(input())
  data = list(map(int, input().split()))
  graph = [[] for _ in range(n + 1)]

  for i in range(1, n + 1):
    graph[i].append(data[i - 1])

  visit = [False] * (n + 1)

  result = 0
    
  for i in range(1, n + 1):
    if not visit[i]: 
      dfs(i)
      result += 1
  print(result)
  

2. 서로소 집합 알고리즘

import sys
input = sys.stdin.readline

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

def union(a, b):
  a = find(a)
  b = find(b)
  if a != b:
    if a < b:
      parent[b] = a
    else:
      parent[a] = b

for t in range(int(input())):
  n = int(input())
  data = [0] + list(map(int, input().split()))
  
  parent = [i for i in range(0, n + 1)]
  cycle = 0

  for a, b in enumerate(data):
    if a == 0:
      continue
    if find(a) == find(b):
      cycle += 1
    else:
      union(a, b)
  
  print(cycle)