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

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

9466번: 텀 프로젝트

  순열 사이클 문제로 접근하여 문제를 해결하였습니다. 깊이우선 탐색으로 한 학생으로부터 선택한 팀원을 깊이우선 깊이 우선 탐색하면서 마지막 학생이 시작한 한 학생을 가르킨다면 사이클이 생기고 이 사이클이 생긴 리스트들을 결과 값에 저장합니다. 또한 자기자신이 자기자신을 뽑은경우는 자기혼자 팀원이 될 수 있습니다.

cycle[cycle.index(newstudent) 자기자신의 Index로 부터 개수를 새면 됩니다.

 

import sys
sys.setrecursionlimit(100001)
T = int(input())


def dfs(student):
    global result
    visited[student] = True
    cycle.append(student)
    newstudent = graph[student]
    
    if visited[newstudent]:
        if newstudent in cycle:
            result += cycle[cycle.index(newstudent):] # 자기자신으로부터 마지막팀원까지 그룹핑
        return
    else:
        dfs(newstudent)

for _ in range(T):
    n = int(input())
    graph = [0] + list(map(int, input().split()))
    result = []
    visited = [False for _ in range(n+1)]
    for i in range(1, n+1):
        if not visited[i]:
            cycle = []
            dfs(i)    
            
    print(n - len(result))