1. T를 입력받는다.
2. 다음 과정을 T번 반복한다.
2-1. 정점의 개수 N을 입력받는다.
2-2. [n+1][] 크기의 리스트 graph를 생성한다.
2-3. data라는 리스트에 연결 정보를 저장한다.
2-4. 1부터 N+1까지 반복하면서 그래프에 연결 정보를 추가한다.
2-5. 방문 여부 확인을 위한 리스트 visited와 순열 사이클의 개수를 카운트 하기 위한 cnt를 초기화한다.
2-6. N개의 정점에 대해, 해당 정점을 아직 방문하지 않았다면 DFS를 수행하고 cnt를 1 증가시킨다.
2-7. cnt를 출력한다.
3. DFS 함수를 구현한다.
import sys
input = sys.stdin.readline
t = int(input())
def dfs(v):
visited[v] = True
for i in graph[v]:
if not visited[i]:
dfs(i)
for i in range(t):
cnt = 0
n = int(input())
graph = [[]for i in range(n+1)]
visited = [False]*(n+1)
data = list(map(int,input().split()))
for i in range(1,n+1):
graph[i].append(data[i-1])
for i in range(1,n+1):
if not visited[i]:
dfs(i)
cnt +=1
print(cnt)
'[BOJ] - Python' 카테고리의 다른 글
[백준] 2468 : 안전 영역 python (0) | 2023.08.22 |
---|---|
[백준] 1525 : 퍼즐 python (0) | 2023.08.19 |
[백준] 11724 : 연결 요소의 개수 python (0) | 2023.08.18 |
[백준] 2644 : 촌수계산 python (0) | 2023.08.18 |
[백준] 1389 : 케빈 베이컨의 6단계 법칙 python (0) | 2023.08.18 |