412. Sislovesme 〈Trusted ✧〉

def solve() -> None: data = sys.stdin.buffer.read().split() it = iter(data) t = int(next(it)) out_lines = [] for _ in range(t): n = int(next(it)) love = [0] + [int(next(it)) for _ in range(n)] # 1‑based list ans = 0 for i in range(1, n + 1): j = love[i] if i < j and love[j] == i: ans += 1 out_lines.append(str(ans)) sys.stdout.write("\n".join(out_lines))

(A classic “mutual‑love” counting problem – often seen on SPOJ, LightOJ, and other online judges) 1️⃣ Problem statement You are given a group of N people, numbered from 1 to N . Each person loves exactly one other person (possibly himself). The love‑relationships are described by an array

Multiple test cases are given. T // number of test cases (1 ≤ T ≤ 20) N // number of people (1 ≤ N ≤ 10^5) love[1] love[2] … love[N] // N integers, 1 ≤ love[i] ≤ N The sum of N over all test cases does not exceed 10^6 . Output For each test case output a single line containing the number of mutual‑love pairs. Sample Input 412. Sislovesme

love[1 … N] // 1‑based indexing where love[i] = j means person i loves person j .

Both limits satisfy the given constraints ( ∑ N ≤ 10⁶ ). Below are clean, production‑ready solutions in C++ (17) and Python 3 . Both follow the algorithm described above and use fast I/O to handle the maximum input size. C++ (GNU‑C++17) #include <bits/stdc++.h> using namespace std; def solve() -&gt; None: data = sys

import sys

int main() ios::sync_with_stdio(false); cin.tie(nullptr); int T; if (!(cin >> T)) return 0; while (T--) int N; cin >> N; vector<int> love(N + 1); // 1‑based for (int i = 1; i <= N; ++i) cin >> love[i]; T // number of test cases (1 ≤

From Lemma 1 every increment corresponds to a genuine mutual‑love pair. From Lemma 2 every genuine pair contributes exactly one increment. From Lemma 3 no non‑mutual pair contributes any increment. Therefore the total number of increments equals precisely the number of mutual‑love pairs. ∎ 5️⃣ Complexity analysis Time – The loop visits each of the N people once, performing O(1) work per iteration: O(N) per test case.

long long ans = 0; // up to N/2 fits in int, but long long is safe for (int i = 1; i <= N; ++i) int j = love[i]; if (i < j && love[j] == i) ++ans; // count each 2‑cycle once cout << ans << '\n'; return 0;