Untitled

mail@pastecode.io avatar
unknown
plain_text
7 months ago
1.5 kB
129
Indexable
Never
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <fstream>
#include <vector>
#include <string>
#include <sstream>
#include <cstring>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <climits>
#include <cmath>
#include <iomanip>
#include <cstdlib>
using namespace std;

#define MAX 1000000000 + 5
//#define M 100 + 5
#define N 1000 + 1
#define MOD (long long)1000000007
#define ll long long
#define ld long double
#define sz size()
#define F(i, a, b) for (int i = a; i < b; i++)
#define FOR(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
#define faster() ios_base::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
#define zero(n) setw(n) << setfill('0')
#define stp(n) fixed << setprecision(n)

int main() {
	int t;
	cin >> t;

	while (t--) {
		int n;
		cin >> n;

		vector<pair<int, int>> v;
		int a;

		for (int i = 0; i < n; i++) {
			cin >> a;
			v.push_back({ a, i });
		}

		sort(v.begin(), v.end());

		bool is_visited[N];
		memset(is_visited, false, sizeof is_visited);
		int ans = 0;

		//for (int i = 0; i < n; i++) {
		//	cout << v[i].first << " " << v[i].second << endl;
		//}

		for (int i = 0; i < n; i++) {
			if (v[i].second == i || is_visited[i] == true) continue;

			int nextNode = i;
			int swap_process = 0;

			while (!is_visited[nextNode]) {
				is_visited[nextNode] = true;
				swap_process++;
				nextNode = v[nextNode].second;
			}
			ans += swap_process - 1;
		}

		cout << ans << endl;
	}

	return 0;
}
Leave a Comment