[못 푼 문제] 백준 9466번

처음에는 각 정점마다 사이클의 시작인지 아닌지만 구분하는 방법으로 코드를 구성하였다. 그렇게 하면 근데 각 정점마다 탐색을 해야하므로 시간이 너무 오래 걸린다. 그래서 모든 정점이 사이클의 시작이 아닌 dfs로 사이클을 찾는 순간 다 처리해준다. 그러면 시간이 줄어든다.

원래 코드는

import sys

def find(stu):
    first = stu
    temp = [first]
    for i in range(n):
        next = team[stu]
        if isTeam[next]:
            break
        if next == first:
            return temp
        temp.append(next)
        stu = next
    return []



for _ in range(int(sys.stdin.readline())):
    n = int(sys.stdin.readline())
    team = list(map(int, sys.stdin.readline().split()))
    team.insert(0, 0)
    isTeam = [False] * (n+1)
    for i in range(1, n+1):
        if not isTeam[i]:
            result = find(i)
            if result:
                for i in result:
                    isTeam[i] = True

    print(isTeam.count(False)-1)

수정된 코드는

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

K = int(input()) # test 수

def dfs(v):
    global result
    visited[v] = 1 # 방문한 정점 기록
    traced.append(v) # 탐색 경로 저장

    w = graph[v] # 다음 방문할 정점
    if visited[w] == 1: # 방문 가능한 곳이 끝났는지 체크
        if w in traced: # 탐색 경로에 다음 방문할 정점이 존재하면 순환
            result += traced[traced.index(w):] # 사이클이 되는 구간부터만 팀을 이룸
        return
    else:
        dfs(w) # 탐색 진행



for _ in range(K):
    V = int(input()) # 학생 수
    graph = [0] + list(map(int, input().split())) # 그래프 생성, 맨 앞에 [0]을 추가해 인덱스에 접근하기 편리하도록.
    visited = [0] * (V+1) # 방문한 정점를 담을 stack 생성
    result = [] # 팀을 구성한 학생 수


    for i in range(1, V+1): # 1번 학생부터 탐색 시작.
        if visited[i] == 0: # 방문한 정점이 아닌 경우에만 탐색 진행
            traced = [] # 탐색 경로 정보를 담을 stack 생성
            dfs(i)

    print(V - len(result))

여기서 알아야 할 점은 리스트 같은 경우 global 선언을 하지 않아도 된다는 점이다.