[BOJ 9466] 텀 프로젝트

방향그래프에서 사이클에 속하는 정점이 몇개인지 알아야 하는 문제
단순히 사이클이 존재하는지 확인하는 것이라면 union-find를 하겠지만 정확히 누가 사이클의 원소인지 파악해야한다.

문제 예시1번이라면
1에서 dfs 시작
trace가 [1, 3]에서 3을 재방문하므로 사이클인 [3]의 크기는 1 리턴
2에서 dfs 시작
trace가 [2] 1을 이미 방문했으므로 끝, 사이클이 없으므로 0 리턴
3은 이미 방문했으므로 dfs 안함
4에서 dfs 시작
trace가 [4, 7, 6]에서 4를 재방문하므로 사이클인 [4, 7, 6]의 크기 3 리턴
5에서 dfs 시작
trace가 [5]에서 3을 이미 방문했으므로 끝, 사이클이 없으므로 0 리턴
6, 7은 이미 방문했으므로 dfs하지 않는다

import sys
#sys.stdin = open('input.txt', 'r')
sys.setrecursionlimit(int(1e5))
input = sys.stdin.readline

def dfs(graph: dict, visit: list, trace: list, cur: int):
    '''
    graph (dict): 인접리스트로 구현한 그래프
    visit (list): 이미 방문한 정점인지 확인하는 리스트
    trace (list): 현재 방문중인 정점들을 저장하는 리스트
    cur (int): 현재 정점
    '''

    # 방문 확인, 방문 리스트 추가
    visit[cur] = True
    trace.append(cur)
    for node in graph[cur]:
        # 방문하지 않았다면 DFS로 계속 탐색
        if not visit[node]:
            return dfs(graph, visit, trace, node)
        # 방문했는데 그 정점이 현재 방문리스트에 있다면 사이클
        # 사이클에 속하는 원소의 개수를 리턴
        elif node in trace:
            idx = trace.index(node)
            return len(trace[idx:])
    
        # 사이클 없음
    # 따라서 사이클의 원소의 개수는 0
    return 0


T = int(input())
for _ in range(T):
    N = int(input())
    graph = {i: [] for i in range(1, N + 1)}
    pick = list(map(int, input().split()))
    for i, p in enumerate(pick, 1):
        graph[i].append(p)

    answer = 0
    visit = [False] * (N + 1)
    for i in range(1, N + 1):
        if not visit[i]:
            trace = []
            answer += dfs(graph, visit, trace, i)
    print(N - answer)