순열 사이클 (백준 10451)

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

10451번: 순열 사이클

---

처음에 그래프를 만들어서 재귀를 했는데 시간 제한으로 실패!

 

실패한 코드

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

t = int(input())

def dfs(v):
    visited[v] = 1 
    for i in range(n + 1):
        if visited[i] == 0 and graph[v][i] == 1:
            dfs(i)

for i in range(t):
    n = int(input())
    visited = [0 for j in range(n + 1)]
    graph = [[0 for k in range(n + 1)] for m in range(n + 1)]
    m = list(map(int, input().split()))
    
    for a, b in enumerate(m):
        graph[a + 1][b] = 1
        graph[b][a + 1] = 1
    
    cnt = 0
    for j in range(1, n + 1):
        if visited[j] == 0:
            dfs(j)
            cnt += 1
    print(cnt)

일차원 배열로 쉽게 해결하기

import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline

t = int(input())

def dfs(v):
    visited[v] = 1 
    next = m[v]
    if visited[next] == 0:
        dfs(next)

for i in range(t):
    n = int(input())
    visited = [0] * (n + 1)
    m = [0] + list(map(int, input().split()))
    
    cnt = 0
    for j in range(1, n + 1):
        if visited[j] == 0:
            dfs(j)
            cnt += 1
    print(cnt)

---

m = [0] + list(map(int, input().split()))

python 리스트 더하기,,, 기본적인 것 까먹지 말기,,,