# 텀 프로젝트
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)) 출력
'Algorithm > BOJ' 카테고리의 다른 글
[백준] 2437번 - 저울 (파이썬) (0) | 2022.01.31 |
---|---|
[백준] 1300번 - K번째 수 (파이썬) (0) | 2022.01.31 |
[백준] 1202번 - 보석 도둑 (파이썬) (0) | 2022.01.30 |
[백준] 17135번 - 캐슬 디펜스 (파이썬) (0) | 2022.01.30 |
[백준] 4195번 - 친구 네트워크 (파이썬) (0) | 2022.01.29 |