并查集

template <class T>
class UnionFindSet
{
public:
	UnionFindSet(size_t n)
		:_ufs(n, -1)
	{}

	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		if (root1 == root2)
			return;
		if (root1 > root2)
			swap(root1, root2);
		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}

	int FindRoot(int x)
	{
		int parent = x;
		while (_ufs[parent] >= 0)
		{
			parent = _ufs[parent];
		}
		return parent;
	}

	bool InSet(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}

	size_t SetSize()
	{
		size_t size = 0;
		for (size_t i = 0; i < _ufs.size(); i++)
		{
			if (_ufs[i] < 0)
			{
				++size;
			}
		}
		return size;
	}
private:
	std::vector<T> _ufs;
};

路径压缩：

template <class T>
class UnionFindSet
{
public:
	UnionFindSet(size_t n)
		:_ufs(n, -1)
	{}

	void Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);
		// 如果在一个集合里面就不需要合并
		if (root1 == root2)
			return;

		// 数据量小的合并到大的集合
		if (abs(_ufs[root1]) < abs(_ufs[root2]))
			std::swap(root1, root2);
		_ufs[root1] += _ufs[root2];
		_ufs[root2] = root1;
	}

	int FindRoot(int x)
	{
		int root = x;
		while (_ufs[root] >= 0)
		{
			root = _ufs[root];
		}
		// 路径压缩
		while (_ufs[x] >= 0)
		{
			int parent = _ufs[x];
			_ufs[x] = root;
			x = parent;
		}
		return root;
	}

	bool InSet(int x1, int x2)
	{
		return FindRoot(x1) == FindRoot(x2);
	}

	size_t SetSize()
	{
		size_t size = 0;
		for (size_t i = 0; i < _ufs.size(); i++)
		{
			if (_ufs[i] < 0)
			{
				++size;
			}
		}
		return size;
	}
private:
	std::vector<T> _ufs;
};

void UnionFindSetTest()
{
	UnionFindSet<int> ufs(10);
	ufs.Union(7, 6);
	ufs.Union(5, 4);
	ufs.Union(7, 5);
	ufs.Union(5, 2);
	ufs.Union(9, 6);
	ufs.Union(0, 1);
	ufs.Union(0, 3);
	ufs.Union(0, 7);

	for (int i = 0; i < 10; i++)
	{
		ufs.FindRoot(i);
	}
}

省份的数量
等式方程的可满足性

图

两种实现策略：矩阵和领接表

矩阵

领接表
两者互补

namespace matrix
{
	template<class V, class W, W MAX_W = INT_MAX, bool Direction = false>
	class Graph
	{
	public:
		//图的创建：
		//1.IO输入 ---不方便测试
		//2.图结构关系写到文件
		//3.手动添加边
		Graph(const V* a, size_t n)
		{
			for (size_t j = 0; j < n; j++)
			{
				_vertexs.push_back(a[j]);
				_indexMap[a[j]] = j;
			}
			_matrix.resize(n);
			for (size_t i = 0; i < n; i++)
			{
				_matrix[i].resize(n, MAX_W);
			}
		}

		size_t GetVertexIndex(const V& v)
		{
			auto it = _indexMap.find(v);
			if (it != _indexMap.end())
			{
				return it->second;
			}
			else
			{
				//assert(false);
				throw invalid_argument("顶点不存在");
				return -1;
			}
		}
		void AddEdge(const V& src, const V& dst, const W& w)
		{
			size_t srci = GetVertexIndex(src);
			size_t dsti = GetVertexIndex(dst);
			_matrix[srci][dsti] = w;
			//无向图
			if (Direction == false)
			{
				_matrix[dsti][srci] = w;
			}
		}

		void Print()
		{
			//顶点
			for (size_t i = 0; i < _vertexs.size(); i++)
			{
				cout << i << "->" << _vertexs[i] << endl;
			}
			cout << endl;
			//矩阵
			printf("#");//所在的行列为顶点
			for (size_t i = 0; i < _vertexs.size(); i++)
				cout << " " << _vertexs[i];
			cout << endl;
			for (size_t i = 0; i < _matrix.size(); i++)
			{
				cout << _vertexs[i] << " ";
				for (size_t j = 0; j < _matrix.size(); j++)
				{
					if (_matrix[i][j] != MAX_W)
					{
						//cout << _vertexs[i] << "->" << _vertexs[j] << ": " << _matrix[i][j] << endl;
						cout << _matrix[i][j] << " ";
					}
					else
					{
						//cout << _vertexs[i] << "->" << _vertexs[j] << ": " << "*" << endl;
						cout << "* ";
					}
				}
				cout << endl;
			}
		}
	private:
		vector<V> _vertexs;			//顶点集合
		map<V, int> _indexMap;		//顶点映射
		vector<vector<W>> _matrix;	//邻接矩阵
	};

	void TestGraph1()
	{
		Graph<char, int, INT_MAX, true> g("abcd", 4);
		g.AddEdge('a', 'b', 1);
		g.AddEdge('a', 'c', 4);
		g.AddEdge('b', 'c', 3);
		g.AddEdge('b', 'b', 8);
		g.AddEdge('c', 'c', 7);
		g.AddEdge('c', 'b', 9);
		g.AddEdge('d', 'a', 2);
		g.AddEdge('d', 'b', 5);

		g.Print();
	}
}