[백준] 10471 : 순열 사이클 - Python

문제

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫째 줄에는 순열의 크기 N (2 ≤ N ≤ 1,000)이 주어진다. 둘째 줄에는 순열이 주어지며, 각 정수는 공백으로 구분되어 있다.

출력

각 테스트 케이스마다, 입력으로 주어진 순열에 존재하는 순열 사이클의 개수를 출력한다.

import sys
sys.stdin = open("input.txt", "rt")
from collections import deque

# dfs 한바퀴 돌면 하나의 연결요소! 즉 순열사이클
def dfs(v):
    ch[v] = 1
    node = data[v] # 다음 번 노드
    if ch[node] == 0:
        ch[node] = 1
        dfs(node)

T = int(input())
for _ in range(T):
    n = int(input())
    data = list(map(int, input().split()))
    data.insert(0,-1)
    ch = [0] * (n+1)
    cnt = 0
    for i in range(1,n+1):
        if ch[i] == 0:
            dfs(i)
            cnt += 1
    print(cnt)

코멘트

그냥 dfs 한번 돌 때 연결고리 하나 찾는 문제 유형이라고 생각했으면 됐다.
한번 dfs를 하면 쭉 돌면서 도달하는 지점이 있었을 것.
또한 연결요소가 하나라서 !!

• 유니온파인드로 해도 되긴 하는데 쉬움