本文涉及知识点

C++图论

LeetCode1722. 执行交换操作后的最小汉明距离

给你两个整数数组 source 和 target ，长度都是 n 。还有一个数组 allowedSwaps ，其中每个 allowedSwaps[i] = [ai, bi] 表示你可以交换数组 source 中下标为 ai 和 bi（下标从 0 开始）的两个元素。注意，你可以按 任意 顺序 多次 交换一对特定下标指向的元素。
相同长度的两个数组 source 和 target 间的 汉明距离 是元素不同的下标数量。形式上，其值等于满足 source[i] != target[i] （下标从 0 开始）的下标 i（0 <= i <= n-1）的数量。
在对数组 source 执行 任意 数量的交换操作后，返回 source 和 target 间的 最小汉明距离 。
示例 1：
输入：source = [1,2,3,4], target = [2,1,4,5], allowedSwaps = [[0,1],[2,3]]
输出：1
解释：source 可以按下述方式转换：

• 交换下标 0 和 1 指向的元素：source = [2,1,3,4]
• 交换下标 2 和 3 指向的元素：source = [2,1,4,3]
  source 和 target 间的汉明距离是 1 ，二者有 1 处元素不同，在下标 3 。
  示例 2：

输入：source = [1,2,3,4], target = [1,3,2,4], allowedSwaps = []
输出：2
解释：不能对 source 执行交换操作。
source 和 target 间的汉明距离是 2 ，二者有 2 处元素不同，在下标 1 和下标 2 。
示例 3：

输入：source = [5,1,2,4,3], target = [1,5,4,2,3], allowedSwaps = [[0,4],[4,2],[1,3],[1,4]]
输出：0

提示：
n == source.length == target.length
1 <= n <= 10⁵
1 <= source[i], target[i] <= 10⁵
0 <= allowedSwaps.length <= 10⁵
allowedSwaps[i].length == 2
0 <= ai, bi <= n - 1
ai != bi

并集查找

每个下标看作一个点，如果两个下标可以交换，则这两个下标对应的点有无向边连接。两个下标能否直接或间接交换$⟺$ 两个点是否在同一连通区域。用并集查找解决。
枚举每个连通区域的下标集v，通过i枚举v的各点
m[s[i]]++,m[t[i]]-- 。m各元素值绝对值之和/2 ，就是本连通区域无法相同的下标。
时间复杂度：O(n)

代码

核心代码

class CUnionFind
{
public:
	CUnionFind(int iSize) :m_vNodeToRegion(iSize)
	{
		for (int i = 0; i < iSize; i++)
		{
			m_vNodeToRegion[i] = i;
		}
		m_iConnetRegionCount = iSize;
	}	
	CUnionFind(vector<vector<int>>& vNeiBo):CUnionFind(vNeiBo.size())
	{
		for (int i = 0; i < vNeiBo.size(); i++) {
			for (const auto& n : vNeiBo[i]) {
				Union(i, n);
			}
		}
	}
	int GetConnectRegionIndex(int iNode)
	{
		int& iConnectNO = m_vNodeToRegion[iNode];
		if (iNode == iConnectNO)
		{
			return iNode;
		}
		return iConnectNO = GetConnectRegionIndex(iConnectNO);
	}
	void Union(int iNode1, int iNode2)
	{
		const int iConnectNO1 = GetConnectRegionIndex(iNode1);
		const int iConnectNO2 = GetConnectRegionIndex(iNode2);
		if (iConnectNO1 == iConnectNO2)
		{
			return;
		}
		m_iConnetRegionCount--;
		if (iConnectNO1 > iConnectNO2)
		{
			UnionConnect(iConnectNO1, iConnectNO2);
		}
		else
		{
			UnionConnect(iConnectNO2, iConnectNO1);
		}
	}

	bool IsConnect(int iNode1, int iNode2)
	{
		return GetConnectRegionIndex(iNode1) == GetConnectRegionIndex(iNode2);
	}
	int GetConnetRegionCount()const
	{
		return m_iConnetRegionCount;
	}
	vector<int> GetNodeCountOfRegion()//各联通区域的节点数量
	{
		const int iNodeSize = m_vNodeToRegion.size();
		vector<int> vRet(iNodeSize);
		for (int i = 0; i < iNodeSize; i++)
		{
			vRet[GetConnectRegionIndex(i)]++;
		}
		return vRet;
	}
	std::unordered_map<int, vector<int>> GetNodeOfRegion()
	{
		std::unordered_map<int, vector<int>> ret;
		const int iNodeSize = m_vNodeToRegion.size();
		for (int i = 0; i < iNodeSize; i++)
		{
			ret[GetConnectRegionIndex(i)].emplace_back(i);
		}
		return ret;
	}
private:
	void UnionConnect(int iFrom, int iTo)
	{
		m_vNodeToRegion[iFrom] = iTo;
	}
	vector<int> m_vNodeToRegion;//各点所在联通区域的索引,本联通区域任意一点的索引，为了增加可理解性，用最小索引
	int m_iConnetRegionCount;
};

class Solution {
		public:
			int minimumHammingDistance(vector<int>& source, vector<int>& target, vector<vector<int>>& allowedSwaps) {
				const int N = source.size();
				CUnionFind uf(N);
				for (const auto& v : allowedSwaps) {
					uf.Union(v[0], v[1]);
				}
				int ans = 0;
				auto m = uf.GetNodeOfRegion();
				for (const auto& [tmp, v] : m) {
					unordered_map<int, int> mCnt;
					for (const auto& i : v) {
						mCnt[source[i]]++;
						mCnt[target[i]]--;
					}
					for (const auto& [tmp, c] : mCnt) {
						ans += abs(c);
					}
				}
				return ans / 2;
			}
		};

单元测试

vector<int> source, target;
		vector<vector<int>> allowedSwaps;
		TEST_METHOD(TestMethod11)
		{
			source = { 1,2,3,4 }, target = { 2,1,4,5 }, allowedSwaps = { {0,1},{2,3} };
			auto res = Solution().minimumHammingDistance(source, target, allowedSwaps);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			source = { 1,2,3,4 }, target = { 1,3,2,4 }, allowedSwaps = {};
			auto res = Solution().minimumHammingDistance(source, target, allowedSwaps);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			source = { 5,1,2,4,3 }, target = { 1,5,4,2,3 }, allowedSwaps = { {0,4},{4,2},{1,3},{1,4} };
			auto res = Solution().minimumHammingDistance(source, target, allowedSwaps);
			AssertEx(0, res);
		}
		TEST_METHOD(TestMethod14)
		{
			source = {2,3,1 }, target = { 1,2,2}, allowedSwaps = { {0,2},{1,2} };
			auto res = Solution().minimumHammingDistance(source, target, allowedSwaps);
			AssertEx(1, res);
		}