백준 - 그래프(# 10451)

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

Code 1

import sys

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

for _ in range(t):
    n = int(sys.stdin.readline())
    num_list = list(map(int, sys.stdin.readline().split()))

    visited = {}
    result = 0

    for i in num_list:
        if i not in visited:
            result += 1
            while i not in visited:
                visited.setdefault(i)
                i = num_list[i-1]

    print(result) 

Code 2

import sys

sys.setrecursionlimit(10000)
def dfs(v):
    visited.setdefault(v)   
    nxt = num_list[v-1]
    if nxt not in visited :
        dfs(nxt)

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    num_list = list(map(int, input().split()))
    visited = {}
    result = 0

    for i in num_list:
        if i not in visited:
            dfs(i)
            result += 1

    print(result)

참고

DFS를 이용하는 방법이 일반적이다.(Code 2)
문제 조건에 의하여 그래프의 모든 요소가 순환한다는 사실을 이용하면 Code 1과 같은 구현할 수도 있다.

이 문제에서 visited를 list로 사용하는 것보다 dict으로 사용하는 것이 빠르다. 어떤 원소가 dict에 포함되어 있는지 확인하는 것이 list에 포함되어 있는지 확인하는 것 보다 빠르다.
여기서 visited를 list로 하면, "시간초과"가 되었지만, dict으로 바꾸니 통과하였다.