Minimum Swaps 2

  • + 1 comment
    #include <bits/stdc++.h>
    
    int main () {
        
        int n;
        std::cin >> n;
        
        std::vector<int> nums(n);
        for (auto& val : nums) {
            std::cin >> val;
            --val;
        }
        
        int ans = 0;
        for (int start = 0; start < n; ++start) {
            if (nums[start] == -1)
                continue;
                
            int streak = 0;
            for (int cur = start; nums[cur] != -1;) {
                ++streak;
                const int nei = nums[cur];
                nums[cur] = -1;
                cur = nei;
            }
            
            ans += streak - 1;
        }
        
        std::cout << ans << "\n";
        
        return 0;
    }