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

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

728x90

반응형

문제

https://www.acmicpc.net/problem/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 실행 횟수가 사이클이 생긴 횟수와 같아진다.

반응형

from http://wookcode.tistory.com/164 by ccl(A) rewrite - 2021-08-08 13:26:40