9466: 텀 프로젝트

문제 링크

9466: 텀 프로젝트

구현 방식

• 시간초과를 극복하기가 어려웠다 (pypy3은 메모리초과, python3으로 setrecursionlimit(10**6) 설정해서 통과함)
• team list를 이용해서 해결했다
  • 일단, visit list는 반복문 밖에 한 번만 선언해줘도 된다
  • team list는 매 반복문 마다 선언
  • dfs에서, 만약 다음 노드가 방문한 노드인 경우, 해당 노드가 team에 포함되는지를 확인한다
    -> 만약 team에 해당된다면 team[team.index(다음노드):]의 길이를 answer에서 빼준다

코드

import sys
sys.setrecursionlimit(10**6)

def dfs(curr):
    global answer

    visit[curr] = True
    team.append(curr)

    if visit[adj[curr]]:
        if adj[curr] in team:
            answer -= len(team[team.index(adj[curr]):])
    else:
        dfs(adj[curr])


T = int(sys.stdin.readline()[:-1])
for t in range(T):
    N = int(sys.stdin.readline()[:-1])
    adj = [-1]; adj.extend(list(map(int, sys.stdin.readline()[:-1].split())))
    
    answer = N; visit = [False] * (N+1)
    for n in range(1, N+1):
        if not visit[n]:
            team = []; dfs(n)
    print(answer)