BOJ 9466 파이썬 텀 프로젝트

너 사이클 알아? 사이클 찾을 수 있어?라고 묻는 문제다.

어려운 문제는 아니지만 사이클을 구별하는 코드를 짜본 숙련도가

부족하여 애를 먹었다.

숫자 고르기와 거의 똑같은 문제이다.

 

사이클의 정의: 처음 노드(루트 노드)에서 시작하여 다시 처음 노드로 되돌아온다.

 

모든 정점에서 완전 탐색을 하는데

이미 방문한 노드는 방문 처리를 해준다.

이 과정에서 사이클이 아닌 노드가 방문처리가 되어

사이클로 잘 못 판별이 될 수 있는데 이 때 res(cycle) 배열에 그 값이 있나 없나로

해결할수 있다.

그리고 만약 진짜 사이클이 맞다면 사이클의 정의인 처음 노드에서 시작하여 처음 노드로 되돌아온다를

그대로 수행해주면 된다. < res[(res.index(x):] >

 

 

 

import sys
from collections import deque
from itertools import combinations
 
 
sys.setrecursionlimit(100000)
def dfs(x):
    
    if ch[x]==1:
   
               # print(x+1,end=' ')
                if x in res:
                    for z in res[res.index(x):]:
                        #print(z+1,end=' ')
                        temp.add(z)
 
                    #print()
        
 
    else:
        ch[x]=1
        res.append(x)
        y=graph[x]
        dfs(y)
                
                
               
 
if __name__=='__main__':
    #sys.stdin=open("input2.txt", "rt")
    
    t=int(input()) ##테스트케이스의 갯수
 
    for _ in range(t):
        n=int(input()) ##학생의 수
 
        
 
        graph=list(map(int,input().split()))
        graph=[x-1 for x in graph]
        
 
        temp=set() ##사이클을 이루는 원소 저장용
        ch=[-1]*n
        res=[]
        for i in range(n):
            if ch[i]==-1:
                 res=[]
                 dfs(i)
                 
     
 
        print(n-len(temp))