[백준] 10451 - 순열 사이클 (Python)

문제 출처 :

www.acmicpc.net/problem/10451

10451번: 순열 사이클

문제 풀이 :

• DFS로 풀면 각 cycle이 나올때마다 방문 표시를 해주고, 전체 (모든 노드를 통과하는) 반복문에서는 방문 표시가 있을때는 DFS를 하지 않도록 한다면 추가로 cycle을 구분해 주지 않아도 각 싸이클에서만 ans을 더해줄 수 있다.
• 이 문제는 cycle이 정확하기 때문에 (어디서 시작하고 어디서 끝날지 우리가 따로 파악하지 않아도 된다는 말) 그다지 어렵지 않다.

t = int(input())

for _ in range(t):
    n = int(input())
    nums = [0]+ list(map(int,input().split()))
    ans =0
    visited = [1] + [0] * (n)
    for i in range(1,n+1):
        stack = [i]
        if(visited[i]==0):
            ans+=1
            visited[i]=1
        while(stack):
            cur_num = stack.pop()
            n_num = nums[cur_num]
            if(visited[n_num]==0):
                visited[n_num]=1
                stack.append(n_num)

    print(ans)