문제 링크 (opens new window)

풀이

1. DP + DFS
2. dp테이블은 각 노드 숫자에 해당
3. 특정 노드가 시작점이 되었는데 해당 시작지점으로 다시 되돌아온 경우 dp테이블값 초기화
4. 순회 노드의 다음 노드가 시작지점 노드가 되는 경우 서브 그래프가 형성되어 순서가 섞여도 모든 숫자들을 포함할 수 있게 된다.

import Foundation

// 위에 뽑은 애들 갯수와 아래 뽑은 애들 갯수가 동일하면 됨
let N = Int(readLine()!)!
var visited: [Bool] = .init(repeating: false, count: N + 2)
var count: [Int] = .init(repeating: 0, count: N+2)
var adj: [[Int]] = .init(repeating: [], count: N + 2)
var dp: [Int] = .init(repeating: 0, count: N+2)

for i in 1...N {
    adj[i].append(Int(readLine()!)!)
}

func dfs(_ here: Int, _ start: Int, _ depth: Int) {
    visited[here] = true
    for there in adj[here] {
        if there == start {
            dp[there] = depth + 1
        }
        if visited[there] {
            continue
        }
        dfs(there, start, depth + 1)
    }
}

for i in 1...N {
    visited = .init(repeating: false, count: N + 2)
    dfs(i, i, 0)
}


print(dp.filter({$0 != 0}).count)
dp.enumerated().forEach { index, value in
    if value == 0 { return }
    print(index)
}