BOJ 10451 순열 사이클

https://www.acmicpc.net/problem/10451
시간 1초, 메모리 256MB
input :

• T
• N (2 ≤ N ≤ 1,000)
• 정수

output :

• 순열에 존재하는 순열 사이클의 개수

---

인접 노드들은 각각 1개 밖에 없다. 각 노드에 대한 인접 노드를 정리하자. ```python graph = [0] data = list(map(int, sys.stdin.readline().split())) for item in data: graph.append(item) ``` 인접 노드들이 1부터 시작하니 1부터 시작하도록 graph[0]에 0을 추가했다.

어떻게 같은 그룹으로 묶을까??
root노드 방식을 사용하자.
root[now] == root[next_node]이면 한 사이클이 되는 것이다.

    root = [i for i in range(n + 1)]
    def DFS(start):
        global cnt
        visit[start] = True

        next_node = graph[start]
        if root[start] == root[next_node]:
            cnt += 1
        else:
            root[next_node] = root[start]
            DFS(next_node)

root에는 맨 처음 자기 자신으로 초기화를 시켜서 .
인접노드가 자기 자신인 경우도 해결 해준다.

DFS의 동작은.
visit[start] 부터 처리하고,
next_node와 비교해서 root가 다르면
root[next_node]를 root[start]값을 넣어주고.
DFS(next_node)를 실행하자.

import sys
sys.setrecursionlimit(10000)

t = int(sys.stdin.readline())
for i in range(t):
    n = int(sys.stdin.readline())

    graph = [0]
    data = list(map(int, sys.stdin.readline().split()))
    for item in data:
        graph.append(item)

    root = [i for i in range(n + 1)]
    visit = [False] * (n + 1)
    cnt = 0

    def DFS(start):
        global cnt
        visit[start] = True

        next_node = graph[start]
        if root[start] == root[next_node]:
            cnt += 1
        else:
            root[next_node] = root[start]
            DFS(next_node)

    for i in range(1, n + 1):
        if not visit[i]:
            DFS(i)
    print(cnt)

DFS는 언제나 setrecursionlimit가 필요하다.