알고리즘 PS

[Python] 백준 #10451 순열 사이클

on_doing 2021. 1. 16. 18:56
728x90

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

from collections import deque
import sys

N = int(sys.stdin.readline())
for i in range(N):
    que = deque()

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

    visited = [0] * n

    graph = {i: [] for i in range(1, n + 1)}

    List = [0] + list(map(int, sys.stdin.readline().rstrip().split()))

    for j in range(1, n + 1):
        graph[j].append(List[j])
    cnt = 0

    for j in range(1, n + 1):
        if visited[j - 1] == 0:
            que.append(j)
            while que:
                p = que.popleft()
                visited[p - 1] = 1
                if visited[graph[p][0] - 1] == 0:
                    que.append(graph[p][0])
                else:
                    break

            cnt += 1
    print(cnt)
728x90