本文涉及知识点

C++图论

LeetCode947. 移除最多的同行或同列石头

n 块石头放置在二维平面中的一些整数坐标点上。每个坐标点上最多只能有一块石头。
如果一块石头的 同行或者同列 上有其他石头存在，那么就可以移除这块石头。
给你一个长度为 n 的数组 stones ，其中 stones[i] = [xi, yi] 表示第 i 块石头的位置，返回 可以移除的石子 的最大数量。
示例 1：
输入：stones = [[0,0],[0,1],[1,0],[1,2],[2,1],[2,2]]
输出：5
解释：一种移除 5 块石头的方法如下所示：

1. 移除石头 [2,2] ，因为它和 [2,1] 同行。
2. 移除石头 [2,1] ，因为它和 [0,1] 同列。
3. 移除石头 [1,2] ，因为它和 [1,0] 同行。
4. 移除石头 [1,0] ，因为它和 [0,0] 同列。
5. 移除石头 [0,1] ，因为它和 [0,0] 同行。
   石头 [0,0] 不能移除，因为它没有与另一块石头同行/列。
   示例 2：
   输入：stones = [[0,0],[0,2],[1,1],[2,0],[2,2]]
   输出：3
   解释：一种移除 3 块石头的方法如下所示：
6. 移除石头 [2,2] ，因为它和 [2,0] 同行。
7. 移除石头 [2,0] ，因为它和 [0,0] 同列。
8. 移除石头 [0,2] ，因为它和 [0,0] 同行。
   石头 [0,0] 和 [1,1] 不能移除，因为它们没有与另一块石头同行/列。
   示例 3：
   输入：stones = [[0,0]]
   输出：0
   解释：[0,0] 是平面上唯一一块石头，所以不可以移除它。
   提示：
   1 <= stones.length <= 1000
   0 <= xi, yi <= 10⁴
   不会有两块石头放在同一个坐标点上

并集查找

n = stones.length
石头看成点，同行或同列看成边。一个连通区域有n个节点，则最多移除n-1个石头，因为最后一个石头无法移动。
如果这个连通区域没有环，则按任意节点为根的树的拓扑序移除。一定能移除n-1个石头。
如果这个连通区域环，则按BFS或DFS搜索树的拓扑序移除。
结论：有多少个连通区域，就有多少块石头无法移动。
答案就是：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 removeStones(vector<vector<int>>& stones) {
				vector<vector<int>> rows(10001), cols(10001);
				for (int i = 0; i < stones.size(); i++) {
					rows[stones[i][0]].emplace_back(i);
					cols[stones[i][1]].emplace_back(i);
				}
				CUnionFind uf(stones.size());
				for (const auto& v : rows) {
					for (int i = 1; i < v.size(); i++) {
						uf.Union(v[i], v[i - 1]);
					}
				}
				for (const auto& v : cols) {
					for (int i = 1; i < v.size(); i++) {
						uf.Union(v[i], v[i - 1]);
					}
				}
				return stones.size() - uf.GetConnetRegionCount();
			}
		};

核心代码

vector<vector<int>> stones;
		TEST_METHOD(TestMethod11)
		{
			stones = { {0,0},{0,1},{1,0},{1,2},{2,1},{2,2} };
			auto res = Solution().removeStones(stones);
			AssertEx(5, res);
		}
		TEST_METHOD(TestMethod12)
		{
			stones = { {0,0},{0,2},{1,1},{2,0},{2,2} };
			auto res = Solution().removeStones(stones);
			AssertEx(3, res);
		}
		TEST_METHOD(TestMethod13)
		{
			stones = { {0,0}};
			auto res = Solution().removeStones(stones);
			AssertEx(0, res);
		}