[백준] 9466번 문제 (텀 프로젝트) 파이썬(Python) 풀이

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

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

def dfs(x):
    global cycle
    visited[x] = True
    temp_cycle.append(x)
    num = arr[x]

    if visited[num]:
        if num in temp_cycle:
            cycle += temp_cycle[temp_cycle.index(num):]
        return
    else:
        dfs(num)

t = int(input())

for _ in range(t):
    n = int(input())
    arr = [0] + list(map(int, input().split()))
    visited = [False] * (n + 1)
    cycle = []

    for i in range(1, n + 1):
        if not visited[i]:
            temp_cycle = []
            dfs(i)

    print(n - len(cycle))

dfs를 통해 방문하지 않은 임의의 노드부터 탐색을 시작한다. 그와 동시에 temp_cycle에 해당 노드를 append 해준다.

이를 반복하다가, 사이클이 형성되면 cycle에 해당 노드드를 append 해주고 마지막에 n - len(cycle)를 출력해주며

답을 구한다.