Baekjoon Online Judge 10451번 파이썬

문제 링크
https://www.acmicpc.net/problem/10451

10451번: 순열 사이클

배열의 인덱스 1,2,3,…을 이용하는 것이라서 graph를 따로 만들어서 풀 필요가 없었다.
dfs를 한번 실행했어도 방문하지 않은 노드가 남아있는 것이라면 순열 사이클의 개수가 더 남아있는 것이다.



정답 코드

import sys
sys.setrecursionlimit(10 ** 6)

T = int(sys.stdin.readline())

def dfs(start):
  visited[start] = True
  next = nodes[start]
  if not visited[next]:
    dfs(next)

for i in range(T):
  N = int(sys.stdin.readline())
  graph = [[] for i in range(N+1)]
  nodes = [0] + list(map(int,sys.stdin.readline().split()))

  
  visited = [False] * (N+1)
  result = 0
  for i in range(1,N+1):
    if not visited[i]:
      dfs(i)
      result += 1
  print(result)