[백준] 9466번: 텀 프로젝트

💻 문제 - G3

순환사이클을 형성해야만 팀이 될 수 있다.

👉 제출 코드

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def dfs(v):
    global result
    visited[v] = 1
    cycle.append(v)
    next = stu[v]
    if not visited[next]:
        dfs(next)
    else:
        # 순열 사이클인지 아닌지
        if next in cycle:
            result += cycle[cycle.index(next):]
        return
for _ in range(int(input())):
    n = int(input())
    stu = [0] + list(map(int, input().split()))
    visited = [0] * (n+1)
    result = []
    for i in range(1, n+1):
        if not visited[i]:
            cycle = []
            dfs(i)
    print(n-len(result))

• 10 ** 6만큼 충분한 재귀 깊이를 주어 오류를 예방한다.
• 사이클을 이루는 팀을 확인하기 위해 cycle 배열을 사용한다.
• dfs로 순열 사이클을 탐색한다.