/*
Prob
2021 SCPC 예선 1번 친구들
*/
#include <bits/stdc++.h>
#include <fstream>
#define N 100010
using namespace std;
int tc, n;
int arr[N], ds[N];
void uni(int a, int b) {
if (a > b) swap(a, b);
ds[a] = b;
}
int find(int a) {
if (ds[a] == a) return a;
return ds[a] = find(ds[a]);
}
int solve() {
int ans = 0;
for (int i = 1; i <= n; i++) ds[i] = i;
for (int i = 1; i <= n; i++) {
if (arr[i] + i > n) continue;
uni(find(i), find(arr[i] + i));
}
for (int i = 1; i <= n; i++)
if (ds[i] == i) ans++;
return ans;
}
int main(void) {
freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(0);
cin >> tc;
for (int tt = 1; tt <= tc; tt++) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> arr[i];
cout << "Case #" << tt << "\n";
cout << solve() << "\n";
}
return 0;
}
'Coding Test > codeground' 카테고리의 다른 글
[SCPC 2021 1차 예선 3번] No Cycle (0) | 2022.06.27 |
---|---|
[SCPC 2021 1차 예선] 이진수 (0) | 2022.06.25 |
[SCPC 1회 예선] 등차수열 (0) | 2022.01.05 |
회로판 위의 배터리 / SCPC 1차 예선 (0) | 2022.01.04 |
균일수 / SCPC 1차 예선 (0) | 2021.11.23 |
Comment