3695. Maximize Alternating Sum Using Swaps

You are given an integer array nums.

You want to maximize the alternating sum of nums, which is defined as the value obtained by adding elements at even indices and subtracting elements at odd indices. That is, nums[0] - nums[1] + nums[2] - nums[3]...

You are also given a 2D integer array swaps where swaps[i] = [pi, qi]. For each pair [pi, qi] in swaps, you are allowed to swap the elements at indices pi and qi. These swaps can be performed any number of times and in any order.

Return the maximum possible alternating sum of nums.

int uf[101010];
int find(int u) {
    return uf[u] == u ? u : uf[u] = find(uf[u]);
}
void uni(int u, int v) {
    int pu = find(u), pv = find(v);
    uf[pu] = uf[pv] = min(pu,pv);
}
class Solution {
public:
    long long maxAlternatingSum(vector<int>& nums, vector<vector<int>>& swaps) {
        iota(begin(uf), end(uf), 0);
        for(auto& s : swaps) uni(s[0], s[1]);
        unordered_map<int, vector<int>> vals;
        unordered_map<int, int> add;
        for(int i = 0; i < nums.size(); i++) {
            int pi = find(i);
            vals[pi].push_back(nums[i]);
            if(i % 2 == 0) add[pi]++;
        }
        long long res = 0;
        for(auto& [k,v] : vals) {
            sort(rbegin(v), rend(v));
            int plus = add[k];
            for(int i = 0; i < v.size(); i++) res += v[i] * (i < plus ? 1 : -1);
        }
        return res;
    }
};