[BOJ] 9466 / 텀 프로젝트 / Python 파이썬

[BOJ] 9466 / 텀 프로젝트 / Python 파이썬

[BOJ] 9466 / 텀 프로젝트 / Python 파이썬

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

9466번: 텀 프로젝트

 

풀이

순환되는 graph 를 찾는 문제이다.

 

키 포인트는 마지막 node 와 첫 node 가 이어져서 Loop 를 이룬다는 것이다.

 

순환되는 graph 를 찾는 방법은 다음과 같다

• 방문 node 를 check 하며 순회
• 거쳐간 node 를 재방문 하였을때 순회 종료
• 마지막 node 와 이어진 node 의 index 부터 grpah 를 구성

 

loop = "순회한 node 를 저장"
t = "마지막 node 가 가르키는 node"

# 순회한 graph 에서 Loop 만들기
loop = loop[loop.index(t):]

 

 

T = int(input())

for _ in range(T):
    N = int(input())
    picks = [0] + list(map(int, input().split()))

    visited = [0] * (N+1)
    res = 0

    for i in range(1, N+1):
        if visited[i]:
            continue
        f = i
        loop = [f]
        visited[f] = 1
        while True:
            t = picks[f]
            if visited[t]:
                break
            f = t
            loop.append(f)
            visited[f] = 1

        if loop and t in loop:
            res += len(loop[loop.index(t):])
    print(N - res)