• Home
  • About
    • JOOS photo

      JOOS

      Joos's blog

    • Learn More
    • Email
    • Github
  • Posts
    • All Posts
    • All Tags
  • Projects

[백준] 10451번 : 순열 사이클 with python3

27 Sep 2018

Reading time ~1 minute

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

import sys
sys.setrecursionlimit(10**6)
read = lambda : sys.stdin.readline().strip()

def dfs(graph, visited, i, i_next):
	# i에서 연결된 노드가 i_next이다.
	if visited[i_next]: return
	# 이미 i에 연결된 노드를 방문했으면 그냥 끝
	visited[i_next] = True
	# 처음이면
	dfs(graph, visited, i_next, graph[i_next])
	# 걔와 연관된 애들을 계속 방문한다. 방문하면서 그 연결된 애들을 다 True로 만들어놓고
	# 그러면 한 사이클에 연관된 애들은 다 방문한 노드가 되고 할일 다했으니 이제 끝낸다.
	return 1

for _ in range(int(read())):
	n = int(read())
	graph = [0] + list(map(int, read().split()))

	visited = [False] * (n + 1)
	res = 0
	for i in range(1, n + 1):
		if dfs(graph, visited, i, graph[i]) == 1:
			res += 1
	print(res)



algorithm백준 Share Tweet +1