정말 어려운 문제였다.
풀이를 봐도 어려워서 5번 넘게 봤다.
두고두고 보고 복습하기 위해 기록한다.
풀이는 간단하지만 시간초과가 난다.
#include <bits/stdc++.h>
using namespace std;
int n;
int arr[100005];
bool iscycle(int idx) {
int cur = idx;
for(int i = 0; i < n; i++) {
cur = arr[cur];
if(cur == idx) return true;
}
return false;
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) {
cin >> n;
for(int i = 1; i <= n; i++) cin >> arr[i];
int ans = 0;
for(int i = 1; i <= n; i++) {
// 끝까지 자기 자신 만나지 못한 사람 => 사이클 형성 못한 사람
if(!iscycle(i)) ans++;
}
cout << ans << '\n';
}
}
#include <bits/stdc++.h>
using namespace std;
int arr[100005];
int n;
int state[100005];
const int NOT_VISITED = 0;
const int CYCLE_IN = -1;
void run(int x) {
int cur = x;
while(true) {
// 매번 다른 값을 넣어 체크
state[cur] = x;
cur = arr[cur];
// 이번 방문에서 도달
if(state[cur] == x) {
while(state[cur] != CYCLE_IN) {
state[cur] = CYCLE_IN;
cur = arr[cur];
}
return;
}
// 이전 방문
else if(state[cur] != 0) return;
}
}
int main(void) {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--) {
cin >> n;
fill(state+1, state+n+1, 0);
for(int i = 1; i <= n; i++) cin >> arr[i];
int ans = 0;
for(int i = 1; i <= n; i++) {
if(state[i] == NOT_VISITED) run(i);
}
int cnt = 0;
for(int i = 1; i <= n; i++) {
if(state[i] != CYCLE_IN) cnt++;
}
cout << cnt << '\n';
}
}