[백준] 10451 : 순열 사이클 python

1. T를 입력받는다.

2. 다음 과정을 T번 반복한다.

    2-1. 정점의 개수 N을 입력받는다.

    2-2. [n+1][] 크기의 리스트 graph를 생성한다.

    2-3. data라는 리스트에 연결 정보를 저장한다.

    2-4. 1부터 N+1까지 반복하면서 그래프에 연결 정보를 추가한다.

    2-5. 방문 여부 확인을 위한 리스트 visited와 순열 사이클의 개수를 카운트 하기 위한 cnt를 초기화한다.

    2-6. N개의 정점에 대해, 해당 정점을 아직 방문하지 않았다면 DFS를 수행하고 cnt를 1 증가시킨다.

    2-7. cnt를 출력한다.

3. DFS 함수를 구현한다.

 

import sys
input = sys.stdin.readline

t = int(input())

def dfs(v):
    visited[v] = True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

for i in range(t):
    cnt = 0
    n = int(input())
    graph = [[]for i in range(n+1)]
    visited = [False]*(n+1)
    data = list(map(int,input().split()))
    for i in range(1,n+1):
        graph[i].append(data[i-1])
    for i in range(1,n+1):
        if not visited[i]:
            dfs(i)
            cnt +=1
    print(cnt)