本文涉及知识点

C++图论 并集查找

LeetCode1319. 连通网络的操作次数

用以太网线缆将 n 台计算机连接成一个网络，计算机的编号从 0 到 n-1。线缆用 connections 表示，其中 connections[i] = [a, b] 连接了计算机 a 和 b。
网络中的任何一台计算机都可以通过网络直接或者间接访问同一个网络中其他任意一台计算机。
给你这个计算机网络的初始布线 connections，你可以拔开任意两台直连计算机之间的线缆，并用它连接一对未直连的计算机。请你计算并返回使所有计算机都连通所需的最少操作次数。如果不可能，则返回 -1 。
示例 1：

输入：n = 4, connections = [[0,1],[0,2],[1,2]]
输出：1
解释：拔下计算机 1 和 2 之间的线缆，并将它插到计算机 1 和 3 上。
示例 2：

输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]]
输出：2
示例 3：
输入：n = 6, connections = [[0,1],[0,2],[0,3],[1,2]]
输出：-1
解释：线缆数量不足。
示例 4：
输入：n = 5, connections = [[0,1],[0,2],[3,4],[2,3]]
输出：0
提示：
1 <= n <= 10⁵
1 <= connections.length <= min(n*(n-1)/2, 10⁵)
connections[i].length == 2
0 <= connections[i][0], connections[i][1] < n
connections[i][0] != connections[i][1]
没有重复的连接。
两台计算机不会通过多条线缆连接。

并集查找

性质一：n-1根电缆一定可以连接n台电脑，第i号电脑连接第i+1号电脑。
性质二：n个节点的连通区域，如果边数大于等于n，则一定有环。如果没环，则任意节点为起点，任意一条边经过的点都是新节点。n条边经过n个节点，加上初始起点共n+1个顶点。与n个节点，矛盾。
推论一：n个节点，m个连通区域，如果边超过n-m，则一定有环。可以从环取一条边，去连两个连通区域。当电缆数 > n-2。即 >= n-1是，如果连通区域超过2，可以连通，直到区域为1。
结论一：如果电缆线少于n-1根，则无法连通。如果大于等于n-1根，则一定能连通。
结论二：连通两个连通区域需要一次操作，故答案就是：连通区域数-1。

代码

核心代码

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 makeConnected(int n, vector<vector<int>>& connections) {
				CUnionFind uf(n);
				for (const auto& v : connections) {
					uf.Union(v[0], v[1]);
				}
				if (connections.size() + 1 < n) { return -1; }
				return uf.GetConnetRegionCount() - 1;
			}
		};

单元测试

int n;
		vector<vector<int>> connections;
		TEST_METHOD(TestMethod11)
		{
			n = 4, connections = { {0,1},{0,2},{1,2} };
			auto res = Solution().makeConnected(n, connections);
			AssertEx(1, res);
		}
		TEST_METHOD(TestMethod12)
		{
			n = 6, connections = { {0,1},{0,2},{0,3},{1,2},{1,3} };
			auto res = Solution().makeConnected(n, connections);
			AssertEx(2, res);
		}
		TEST_METHOD(TestMethod13)
		{
			n = 6, connections = { {0,1},{0,2},{0,3},{1,2} };
			auto res = Solution().makeConnected(n, connections);
			AssertEx(-1, res);
		}
		TEST_METHOD(TestMethod14)
		{
			n = 5, connections = { {0,1},{0,2},{3,4},{2,3} };
			auto res = Solution().makeConnected(n, connections);
			AssertEx(0, res);
		}