백준 - 그래프 (# 9466)

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

Code

import sys

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

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

    for node in range(1,n+1):
        if visited[node] == 0:
            path = []

            while True :
                visited[node] = 1
                path.append(node)
                node = s[node]
                if visited[node] != 0:
                    if node in path:
                        i = path.index(node)
                        for j in path[:i]:
                            visited[j] = -1
                    else:
                        for j in path:
                            visited[j] = -1
                    break
                    
    print(visited.count(-1))

참고

주어진 조건의 그래프에서 사이클을 이루지 못하는 노드의 개수를 세는 문제이다.

0 : 아직 방문하지 않은 노드
1 : 사이클을 이룬 노드
-1 : 사이클을 이루지 못한 노드

이렇게 표시하여 문제를 해결하였다.

처음에는 방문한 노드의 인덱스를 리스트에 따로 기록하고

if __ in  list :

로 리스트에 노드가 있는지 확인하는 방법으로 시도하였는데, 시간초과가 된다. in은 시간이 오래 걸린다.
위의 코드처럼 리스트를 놓고 Boolean이나 숫자로 표시하고 확인하는 것이 빠르다.