백준 | 순열 사이클

백준 순열 사이클

문제에서 주어진 순열은 각 요소가 정확히 하나의 위치로 연결된 그래프이다. 각 노드는 하나의 다음 노드로만 이동할 수 있으므로, 이 그래프는 무조건 사이클을 형성한다.

dfs()가 시작되는 시점은 방문되지 않은 노드를 만났을 때이므로, dfs()가 시작되면 해당 노드를 포함하는 사이클을 전부 탐색하게 된다!

import sys


def dfs(graph, visited, u):
    stack = [u]

    while stack:
        v = stack.pop()

        if not visited[v]:
            visited[v] = True
            stack.append(graph[v])


t = int(sys.stdin.readline().strip())
for _ in range(t):
    n = int(sys.stdin.readline())
    permutation = [0] + list(map(int, sys.stdin.readline().split()))
    visited = [False] * (n + 1)

    cycle_count = 0
    for u in range(1, n + 1):
        if not visited[u]:
            dfs(permutation, visited, u)
            cycle_count += 1

    print(cycle_count)