fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using ll = long long;
  4.  
  5. int main() {
  6.     ios::sync_with_stdio(false);
  7.     cin.tie(nullptr);
  8.  
  9.     int t;
  10.     cin >> t;
  11.     while (t--) {
  12.         int n;
  13.         cin >> n;
  14.  
  15.         vector<int> p(n+1);
  16.         for (int i = 1; i <= n; i++) {
  17.             cin >> p[i];
  18.         }
  19.  
  20.         vector<bool> visited(n+1, false);
  21.         ll ans = 0;
  22.  
  23.         for (int i = 1; i <= n; i++) {
  24.             if (!visited[i]) {
  25.                 // Follow this cycle
  26.                 int curr = i;
  27.                 int length = 0;
  28.                 while (!visited[curr]) {
  29.                     visited[curr] = true;
  30.                     curr = p[curr];
  31.                     length++;
  32.                 }
  33.                 // If its length >= 3, it costs floor(length/2) swaps
  34.                 if (length >= 3) {
  35.                     ans += ((length - 1)/ 2);
  36.                 }
  37.                 // length=1 or 2 cost zero swaps
  38.             }
  39.         }
  40.  
  41.         cout << ans << "\n";
  42.     }
  43.  
  44.     return 0;
  45. }
  46.  
Success #stdin #stdout 0.01s 5312KB
comments (?)
stdin
copy 
6
5
1 2 3 4 5
5
5 4 3 2 1
5
2 3 4 5 1
4
2 3 4 1
3
1 3 2
7
2 3 1 5 6 7 4
stdout
copy 
0
0
2
1
0
2
https://ideone.com/tNmJHl
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!