Minimize Position Mismatches Using Allowed Swaps

### Problem `source` and `target` have equal length. An entry `[a,b]` in `allowedSwaps` permits exchanging source positions a and b any number of times, in any order with other permitted swaps. Return the smallest achievable number of indices where source differs from target. ```cpp class Solution { public: int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps); }; ``` ### Examples **Example 1:** ```text source = [1,3,2], target = [2,1,3], allowedSwaps = [[0,1],[1,2]] Output: 0 Explanation: The connected swap graph permits all three values to be rearranged. ``` **Example 2:** ```text source = [1,1,2,4], target = [1,2,2,3], allowedSwaps = [[0,1]] Output: 2 Explanation: One of the first two positions and the final position must differ. ``` ### Constraints - `n == source.length == target.length`, with `1 <= n <= 10^5`. - Source and target values are in `[1,10^5]`. - `0 <= allowedSwaps.length <= 10^5`. - Each allowed pair has two distinct endpoints in `[0,n-1]`. ### Clarifying Questions Only source is rearranged conceptually. A chain of allowed swaps can move a value between positions without a direct edge. ```hint Inspect the structure Which array may change, and what makes an individual swap legal? ``` ### Reasoning checkpoints - Account for values that can move through a sequence of permitted swaps. - Prove the minimum mismatch count while respecting repeated-value multiplicities. ### Optional extensions How would you also construct a sequence of swaps attaining the minimum?