[백준] 10451 - 순열 사이클 [Python(파이썬)]

문제

www.acmicpc.net/problem/10451

10451번: 순열 사이클

 

풀이

연결 요소의 개수 문제와 상당히 유사한 문제였다.

DFS로 풀 수 있는 기본적인 그래프 문제로, 인덱싱할 때만 주의하면 된다.

 

 

코드

import sys, collections
sys.setrecursionlimit(10**6)

def make_graph(n, p):
    g = collections.defaultdict(int)
    for i in range(1, n+1):
        g[i] = p[i-1]
    return g        

def dfs(u):
    global g
    global visited

    visited[u] = 1

    if not visited[g[u]]:
        dfs(g[u])

t = int(sys.stdin.readline().strip())

for _ in range(t):
    n = int(sys.stdin.readline().strip())
    p = [int(x) for x in sys.stdin.readline().split()]
    cnt = 0

    g = make_graph(n, p)
    visited = [0 for _ in range(n+1)]

    for i in range(1, n+1):
        if not visited[i]:
            dfs(i)
            cnt += 1
    
    print(cnt)