Avengers Alliance

Author : R.i.s.h.i_99

Required Knowledge : Arrays

Time Complexity : $\mathcal{O}(N)$

Editorialist : R.i.s.h.i_99

Approach:

Check for every Avenger if $a[a_i] = i$, count such pairs, and divide the total by $2$ to avoid double counting.

Setter's Code:

#include <bits/stdc++.h>
using namespace std;

int main() {    
    int t;
    cin >> t;
    while (t--) {
        int n;
        cin >> n;
        vector<int> a(n + 1);
        for (int i = 1; i <= n; ++i) cin >> a[i];

        int cnt = 0;
        for (int i = 1; i <= n; ++i) {
            int fav = a[i];
            if (fav >= 1 && fav <= n && a[fav] == i)
                cnt++;
        }
        cout << cnt / 2 << "\n";
    }
}

Tester's Code:

t = int(input())
for _ in range(t):
    n = int(input())
    a = [0] + list(map(int, input().split()))
    cnt = 0

    for i in range(1, n + 1):
        fav = a[i]
        if 1 <= fav <= n and a[fav] == i:
            cnt += 1

    print(cnt // 2)