Minimum Swaps 2

  • + 0 comments

    O(n)

    int minimumSwaps(int n, const vector<int>& arr) {
        vector<vector<int>> cycles;
        vector<bool> visited(n+1);
        for (int i = 1; i <= n; ++i) {
            if (visited[arr[i]]) continue;
            cycles.push_back({arr[i]});
            int travel = arr[i];
            visited[travel] = true;
            while (arr[travel] != cycles.back()[0]) {
                cycles.back().push_back(arr[travel]);
                travel = arr[travel];
                visited[travel] = true;
            }
        }
        int moves = 0;
        for (vector<int> cycle : cycles) moves = moves + cycle.size() - 1;
        return moves;
    }
    
    int main()
    {
        int n, k;
        vector<int> arr = {-1};
        cin >> n;
        for (int i=1; i <= n; ++i) {
            cin >> k;
            arr.push_back(k);
        }
        cout << minimumSwaps(n, arr);
    }