fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3.  
  4. using namespace std;
  5.  
  6. const int MOD = 1e9 + 7;
  7.  
  8. void solve(){
  9. 	int n;
  10. 	cin >> n;
  11.  
  12. 	vector<int> a(n + 1);
  13.  
  14. 	for(int i = 1; i <= n; i++)cin >> a[i];
  15.  
  16. 	int ans = 0;
  17.  
  18.  
  19. 	map<int, int> m;
  20. 	for(int i = 1; i <= n; i++){
  21. 		m[a[i]] = i;
  22. 	}
  23.  
  24. 	for(int i = 0; i < n; i++){
  25. 		if(a[i] == i || a[a[i]] == i)continue;
  26. 		ans++;
  27. 		m[a[a[i]]] = m[i];
  28. 		swap(a[m[i]], a[a[i]]);
  29.  
  30.  
  31. 	}
  32. 	cout << ans << "\n";
  33. }
  34.  
  35. int main(){
  36. 	ios_base::sync_with_stdio(false);
  37. 	cin.tie(nullptr);
  38.  
  39. 	int t = 1;
  40. 	cin >> t;
  41.  
  42. 	for(int i = 1; i <= t; i++){
  43. 		solve();
  44. 	}
  45. 	return 0;
  46. }
Success #stdin #stdout 0s 5276KB
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/jRbOKI
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 hours 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!