알고리즘/Python

[백준/Python] 10451번: 순열 사이클

_SIHA_ 2022. 3. 5. 04:09

📖  문제 링크

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

 

10451번: 순열 사이클

1부터 N까지 정수 N개로 이루어진 순열을 나타내는 방법은 여러 가지가 있다. 예를 들어, 8개의 수로 이루어진 순열 (3, 2, 7, 8, 1, 4, 5, 6)을 배열을 이용해 표현하면 \(\begin{pmatrix} 1 & 2 &3&4&5&6&7&8 \\  3

www.acmicpc.net

 

 

✅  최종 코드

import sys
input = sys.stdin.readline
sys.setrecursionlimit(2000)

t = int(input())


def dfs(x):
    check_dfs[x] = True
    for i in arr[x]:
        if check_dfs[i] == False:
            dfs(i)
            

for i in range(t):
    sum = 0
    n = int(input())
    arr = [[] for i in range(n+1)]
    temp = list(map(int, input().split()))
    check_dfs = [False] * (n+1)
    for j in range(1, n+1):
        arr[j].append(temp[j-1])
        
    for k in range(1, n+1):
        if check_dfs[k] == False:
            dfs(k)
            sum+=1
           
    
    print(sum)