[BaekJoon] 백준 9466번 : 텀 프로젝트

9466번 : 텀 프로젝트

그래프에서 사이클을 찾고 사이클을 이루는 노드 개수를 구하면 되는 문제이다.

시간초과가 엄청 많았는데 전혀 생각지도 못한 부분에 있었다.

노드를 관리하기 편하게 하기 위해 빈 인덱스 0 을 집어넣는 과정에서 deque 로 만들어 appendleft 를 해주었다.

이게 문제였다.. 아마 리스트를 deque 로 바꾸는데도 꽤나 시간이 걸리는 것 같다.

이 부분을 해결하니 시간초과도 사라졌다.. 내가 생각한 알고리즘이 문제가 아니어서 다행이었다.

---

import sys


def DFS(node, edges, visit):
    now_visit = {}
    now_visit_len = 0
    stack = [node]
    visit[node] = True

    while stack:
        now = stack.pop()
        now_visit[now] = now_visit_len
        now_visit_len += 1

        if not visit[edges[now]]:
            visit[edges[now]] = True
            stack.append(edges[now])

        if edges[now] in now_visit:
            return now_visit_len - now_visit[edges[now]]

    return 0


def solution():
    N = int(input())
    visit = {i + 1: False for i in range(N)}
    edges = [0] + list(map(int, sys.stdin.readline().rsplit()))

    cycle_nodes = 0
    for node in range(1, N + 1):
        if not visit[node]:
            cycle_nodes += DFS(node, edges, visit)

    return N - cycle_nodes


if __name__ == "__main__":
    T = int(input())

    for _ in range(T):
        print(solution())