56 lines
1.2 KiB
Swift
56 lines
1.2 KiB
Swift
func solve() -> Int {
|
|
guard let n = Int(readLine() ?? ""),
|
|
let input = readLine()
|
|
else { return 0 }
|
|
|
|
let choice: [Int] = [0] + input.split(separator: " ").compactMap({Int($0)})
|
|
var visited: [Bool] = Array(repeating: false, count: n+1)
|
|
var done: [Bool] = Array(repeating: false, count: n+1)
|
|
var cnt: Int = 0
|
|
|
|
for i in 1...n {
|
|
if i == choice[i] {
|
|
cnt += 1
|
|
visited[i] = true
|
|
done[i] = true
|
|
}
|
|
}
|
|
|
|
func dfs(_ current: Int) {
|
|
visited[current] = true
|
|
let next = choice[current]
|
|
|
|
if !visited[next] {
|
|
dfs(next)
|
|
}
|
|
else if !done[next] {
|
|
cnt += 1
|
|
var n = next
|
|
while n != current {
|
|
cnt += 1
|
|
n = choice[n]
|
|
}
|
|
}
|
|
|
|
done[current] = true
|
|
}
|
|
|
|
for i in 1...n {
|
|
if !done[i] {
|
|
dfs(i)
|
|
}
|
|
}
|
|
|
|
return n-cnt
|
|
}
|
|
|
|
var ans: [Int] = []
|
|
|
|
if let T = Int(readLine() ?? "") {
|
|
for _ in 0..<T {
|
|
ans.append(solve())
|
|
}
|
|
}
|
|
|
|
print(ans.compactMap({String($0)}).joined(separator: "\n"))
|