Algorithm/etc
cycle 찾기
DingCoDing
2022. 2. 21. 13:49
반응형
#include <bits/stdc++.h>
using namespace std;
int arr[100001];
bool vis[100001];
bool done[100001];
int cnt= 0;
void DFS(int x) {
vis[x] = 1;
int nx = arr[x];
if (!vis[nx]) {
DFS(nx);
}
else if(!done[nx]) {
for (int i = nx; i != x; i = arr[i]) {
cnt++;
}
cnt++;
}
done[x] = 1;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
for (int T = 0; T < t; T++) {
int n;
cin >> n;
memset(arr, 0, sizeof(arr));
memset(vis, 0, sizeof(vis));
memset(done, 0, sizeof(done));
cnt = 0;
for (int i = 1; i <= n; i++) {
cin >> arr[i];
}
for (int i = 1; i <= n; i++) {
if (!vis[i]) {
DFS(i);
}
}
cout << n - cnt << '\n';
}
return 0;
}
DFS로 O(n)으로 cycle을 찾아 낼 수 있다
반응형