[백준] 9466번 - 텀 프로젝트 (파이썬)

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

# 텀 프로젝트
import sys
input = sys.stdin.readline
sys.setrecursionlimit(100001)


def dfs(x):
    global result
    visited[x] = True
    cycle.append(x)
    if visited[student[x]]:
        if student[x] in cycle:
            result += cycle[cycle.index(student[x]):]
        return
    else:
        dfs(student[x])


T = int(input())
for _ in range(T):
    N = int(input())
    student = list(map(int, input().split()))
    student.insert(0, 0)
    visited = [False] * (N+1)
    result = []

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

    print(N-len(result))

 

DFS

1. 1번노드부터 방문하지 않은 노드를 탐색하면서 dfs실행

2. dfs : student리스트를 계속 파고들어가면서 사이클 확인

    - 만약 사이클이 발생하면 cycle리스트에서 해당 노드의 index부터 끝까지 슬라이싱

    - 이후 result에 더해준다

3. result의 길이는 팀을 이룬 학생의 수, N-len(result)) 출력