BOJ 10451번 순열 사이클 파이썬

문제

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

배열 index는 0부터 시작하지만 입력으로 들어오는 값은 1부터이다.

따라서 편의를 위해서 graph랑 visited의 index는 사용 안하는데, 이런 자잘한 부분을 놓치면 index out of range가 발생할 수 있다.

여태 풀어본 dfs 문제에서는 부모 노드가 여러 자식노드를 갖고 있는 형태였는데, 이 문제에서는 최대 한 개 노드까지 밖에 가질 수 없어서 더 간단하다.

import sys
sys.setrecursionlimit(100000)

t = int(input())

def dfs(x):
    global visited
    visited[x] = True
        #아직 방문하지 않았을 때만 방문하고, 방문하면 방문처리
    if not visited[graph[x]]:
        dfs(graph[x])

for i in range(t):
    #초기화
    n = int(input())
    graph = list(map(int,input().split()))
    graph.insert(0,0)

    visited = [False] * (n+1)

    cnt = 0

    for k in range(1,n+1):
        if not visited[k]:
            dfs(k)
            cnt+=1
    print(cnt)