백준 9466번: 텀 프로젝트

BOJ

백준 9466번: 텀 프로젝트

접근

DFS 알고리즘을 사용하여 사이클을 이루지 않는 사람의 수를 구하는 문제이다.

Correct Solution

import sys
input = sys.stdin.readline

sys.setrecursionlimit(10**6)

def dfs(node):
    global result
    visit[node] = True
    cycle.append(node)
    next = graph[node]

    if not visit[next]:
        dfs(next)
    else:
        if next in cycle:
            result += cycle[cycle.index(next):]
        return

for _ in range(int(input())):
    N = int(input())
    graph = [0] + list(map(int, input().split()))

    visit = [False] * (N + 1)
    result = []

    for i in range(1, N + 1):
        if not visit[i]:
            cycle = []
            dfs(i)

    print(N - len(result))

참고 사이트

파이리썬의 파이썬