SHARE
TWEET

Untitled

Mohamed_AIT_RAMI May 31st, 2020 1,420 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #include <algorithm>
  3. #include <string.h>
  4. #include <math.h>
  5. using namespace std;
  6. typedef long long ll;
  7. typedef unsigned long long ull;
  8. const ll mod = 1000000007;
  9.  
  10. #define pf(n) cout << n << endl
  11. #define pfs(n) cout << n
  12. #define ps() cout << " "
  13. #define sf(n) cin >> n
  14. #define in(i,n) for (int i = 0; i < n; i++)
  15. #define vi vector<int>
  16. #define vp vector<pair<int, int>>
  17. #define graph vector< vector<int> >
  18. #define vs vector<string>
  19. const int MAXN = 100005;
  20. /**  '' "Lionel VB" ^ **/
  21. int minSwaps(int arr[], int n) {
  22.     pair<int, int> arrPos[n];
  23.     for (int i = 0; i < n; i++)
  24.     {
  25.         arrPos[i].first = arr[i];
  26.         arrPos[i].second = i;
  27.     }
  28.     sort(arrPos, arrPos + n);
  29.     vector<bool> vis(n, false);
  30.     int ans = 0;
  31.     for (int i = 0; i < n; i++) {
  32.         if (vis[i] || arrPos[i].second == i)
  33.             continue;
  34.         int cycle_size = 0;
  35.         int j = i;
  36.         while (!vis[j]) {
  37.             vis[j] = 1;
  38.             j = arrPos[j].second;
  39.             cycle_size++;
  40.         }
  41.         if (cycle_size > 0)
  42.         {
  43.             ans += (cycle_size - 1);
  44.         }
  45.     }
  46.     return ans;
  47. }
  48. int main() {
  49.     ios::sync_with_stdio(false);
  50.     cin.tie(NULL);
  51.     int n, s;
  52.     cin >> n >> s;
  53.     while(n--){
  54.         ll nod = 0;
  55.         ll l, r;
  56.         string temp;
  57.         int arr[s];
  58.         in(i, s){
  59.             cin >> l >> temp >> r;
  60.             arr[l-1] = r;
  61.         }
  62.         pf(minSwaps(arr, s));
  63.     }
  64.     return 0;
  65. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Top