Baekjoon 9466. 텀 프로젝트 / Python

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

알고리즘 설명

문제 설명

학생들을 그룹으로 묶어야 한다.
그룹의 학생들은 한명이거나, 싸이클을 생성해야한다.

코드 설명

임의의 학생을 기준으로 간선을 따라간다.
처음의 학생을 기록하는 방법이 아니라, 간선을 따라간 다음 학생이 그룹 내부에 있는지를 확인하는 방법으로 사이클을 확인한다.

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

# 재귀 함수로 학생들을 방문하면서 팀을 구성할 수 있는지 확인
def sol(x):
    global res
    visit[x] = 1  # 현재 학생을 방문 표시
    tmp.append(x)  # 현재 학생을 임시 리스트에 추가
    if visit[arr[x]]:  # 만약 다음 학생이 이미 방문한 학생이면
        if arr[x] in tmp:  # 순환 구조가 형성되었는지 확인
            now = tmp.index(arr[x])  # 순환의 시작 인덱스를 찾음
            res -= len(tmp) - now  # 순환 구조에 있는 학생들은 팀에 속함
        return
    sol(arr[x])  # 다음 학생을 재귀적으로 방문

# 여러 테스트 케이스 처리
for _ in range(int(input())):
    res = n = int(input())  # 학생 수와 결과 초기화
    arr = [0] + list(map(int, input().split()))  # 학생 선택 배열
    visit = [0] * (n + 1)  # 방문 여부 배열 초기화
    for i in range(1, n + 1):
        if not visit[i]:  # 방문하지 않은 학생에 대해
            tmp = []  # 임시 리스트 초기화
            sol(i)  # 팀 구성 확인
    print(res)