[BOJ] 9466

seonhyeongpak·2022년 1월 1일
0

python

목록 보기
3/7
import sys
sys.stdin.readline
sys.setrecursionlimit(10**6)
tc=int(input()) # testcase의 갯수 입력받음

def solve(num):
    global result
    check[num]=1 # 방문했다고 표시.
    circuit.append(num) #cycle을 이루는지 확인하기 위해 circuit에 추가.
    tar=arr[num] 
    if check[tar]==1:
        if tar in circuit:
            result+=circuit[circuit.index(tar):] #cycle을 이루는 것이므로 result에 추가.
        return
    else:
        solve(tar)




for i in range(tc):
    l=int(input())
    arr=[0]+list(map(int,input().split())) # index의 편리성을 위해 0 추가
    check=[0]*(l+1)
    result=[]
    for j in range(1,l+1):
        if check[j]==0: # 방문하지 않았으면
            circuit=[]
            solve(j) # dfs탐색
    print(l-len(result))
    ```
profile
모든 생각을 구현해내기 위해 노력하는 개발자

0개의 댓글