1

https://suri78.tistory.com/128 참고

사이클은 visit에 넣는 group 의 숫자로 구분한다.

while visit[i] == 0:
  visit[i] = group
  i = choice[i]

→ 연결된 index들의 visit[index]에 같은 값의 group 숫자를 넣어준다.
이미 다른 group이나 현재 group에 연결된 node를 만나면 순회를 멈춘다.

while visit[i] == group:
  visit[i] = -1
  i = choice[i]

→ 마지막 index 값부터 다시 cycle을 찾는다.
현재 group에 속하는 node 중에서 연결된 값을 찾아본다.

cnt = 0
for v in visit:
	if v > 0:
	cnt += 1

→ 서로 연결된 node들은 visit = -1 이므로 visit != 1 인 것들의 개수를 체크한다.

num_test = int(sys.stdin.readline())

for _ in range(num_test):
    n = int(sys.stdin.readline())
    choice = [0] + list(map(int, list(sys.stdin.readline().strip().split())))
    visit = [0] * (n + 1)

    group = 1
    for i in range(1, n+1):
        if visit[i] == 0:
            while visit[i] == 0:
                visit[i] = group
                i = choice[i]
            while visit[i] == group:
                visit[i] = -1
                i = choice[i]
            group += 1
    cnt = 0
    for v in visit:
        if v > 0:
            cnt += 1
    print(cnt)

2

https://claude-u.tistory.com/435 참고

import sys
sys.setrecursionlimit(111111) #충분한 재귀 깊이를 주어 오류를 예방


def dfs(x):
    global result
    visited[x] = True
    cycle.append(x) #사이클을 이루는 팀을 확인하기 위함
    number = numbers[x]
    
    if visited[number]: #방문가능한 곳이 끝났는지
        if number in cycle: #사이클 가능 여부
            result += cycle[cycle.index(number):] #사이클 되는 구간 부터만 팀을 이룸
        return
    else:
        dfs(number)


for _ in range(int(input())):
    N = int(input())
    numbers = [0] + list(map(int, input().split()))
    visited = [True] + [False] * N #방문 여부
    result = []
    
    for i in range(1, N+1):
        if not visited[i]: #방문 안한 곳이라면
            cycle = []
            dfs(i) #DFS 함수 돌림
            
    print(N - len(result)) #팀에 없는 사람 수