[BOJ] 10451 / 순열 사이클 / Python 파이썬

[BOJ]  10451 / 순열 사이클 / Python 파이썬

[BOJ]  10451 / 순열 사이클 / Python 파이썬

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

10451번: 순열 사이클

 

풀이

순열과 index 로 그려진 graph 의 사이클 수를 구하는 문제이다.

 

순열의 수가 다음 순열의 index 가 된다는 것을 이해하면 쉽게 구할 수 있다.

 

import sys

input = sys.stdin.readline

T = int(input())

for _ in range(T):
    N = int(input())

    nums = list(map(int, input().split()))
    nums = [0] + nums

    cnt = 0

    for f in range(1, N+1):
        if nums[f] < 0:
            continue
        cnt += 1
        t = nums[f]
        nums[f] = -1
        while True:
            if t < 0:
                break
            f = t
            t = nums[f]
            nums[f] = -1
    print(cnt)