[백준][10451][S2] 순열 사이클

---

기본적인 DFS 문제이며, 연결된 부분집합의 개수(사이클)을 세는 문제이다.

DFS를 한 번 호출할 때마다 count를 1씩 올려서 개수를 센다.

 

import sys

T = int(sys.stdin.readline())
for i in range(T):
    N = int(sys.stdin.readline())
    graph = list(map(int, sys.stdin.readline().split()))
    
    #graph는 1번 인덱스부터 사용한다. 0번은 더미 데이터를 넣어주자.
    graph.insert(0, 99999)

    #방문 기록
    visited = [False for i in range(N+1)]
    visited[0] = True

    #-----------------------------------------------------------------------

    def dfs(v):
        visited[v]=True #v 노드는 방문 했다.
        i = graph[v] #v 노드와 연결된 노드를 확인한다.
        if not visited[i]: #만약 연결된 노드를 방문하지 않았다면,
            dfs(i) #그 노드도 재귀 호출로 방문해준다.

    count = 0
    for i in range(len(visited)): 
        if not visited[i]: #만약 i번 노드를 방문하지 않았다면,
            dfs(i) #i번 노드부터 깊이 탐색을 시작한다.
            count += 1
            print(visited)

    print(count)