[python] 백준 9466 텀 프로젝트

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

9466번: 텀 프로젝트

 

문제 해결

• 하나씩 돌아가며 그 안에 사이클이 있는지 확인한다.
• 사이클을 돌면서 한 번 지나간 index는 두 번 지나갈 필요가 없다.(만약 한 번 돌았을 때 사이클이 안만들어 졌으면 안만들어지는 것이다.)

 

CODE

import sys
sys.setrecursionlimit(1000000)
def cycle(num):
    global ans
    visited[num] = True
    c.append(num)
    new_num = A[num]
    if visited[new_num]:
        if new_num in c:
            ans += c[c.index(new_num):]
        return
    else:
        cycle(new_num)

if __name__=='__main__':
    for _ in range(int(input())):
        n = int(input())
        A = [0] + list(map(int, input().split()))
        visited= [0 for _ in range(n+1)]
        ans = []
        for i in range(1,n+1):
            if visited[i] == False:
                c = []
                cycle(i)
        print(n-len(ans))