[백준] 10451번, 순열 사이클 (Python)

문제

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

10451번: 순열 사이클

 

코드

import collections

t = int(input())
queue = collections.deque()

def bfs(index):
    queue.append(index)
    while queue:
        cur = queue.popleft()
        visited[cur] = True
        if visited[graph[cur]] == False:
            visited[graph[cur]] = True
            queue.append(graph[cur])

for i in range(t):
    n = int(input())
    graph = [0]+list(map(int, input().split()))
    visited = [0 for _ in range(n+1)]
    count = 0
    for j in range(1, n+1):
        if visited[j] == False:
            bfs(j)
            count += 1
    print(count)

visited로 방문체크를 해줘서 모든 정점노드들을 for문으로 돌아 방문하지 않은 정점일 경우 bfs를 실행한다.

 

즉, bfs 실행 횟수가 사이클이 생긴 횟수와 같아진다.