并查集

#include<iostream>
#include<vector>
using namespace std;//x是数组的下标

class UnionFindSet
{
public:
	//一开始每一个都表示一个独立的集合
	UnionFindSet(size_t n)
	{
		_v.resize(n, -1);
	}


	int FindRoot(int x)
	{
		//一直找到负数停止
		while (_v[x] >= 0)
		{
			x = _v[x];
		}
		return x;
	}

	//判断x和y是否在一个集合，如果不在那就合并
	bool Union(int x1, int x2)
	{
		int root1 = FindRoot(x1);
		int root2 = FindRoot(x2);

		//如果两个根是相同的，那么这两个数就在一个集合，不相同说明不在一个集合，那就进行合并
		if (root1 == root2)
			return false;
		//走到这里已经说明了两个数不是一个集合的，所以需要合并
		_v[root1] += _v[root2];
		_v[root2] = root1;
		return true;
	}

	//数组中，负数的个数，即为集合的个数
	size_t Count()
	{
		size_t Count = 0;
		for (auto& e : _v)
		{
			if (e < 0)
				++Count;
		}
		return Count;
	}
private:
	vector<int> _v;
};

b树

反向指针：找父亲
把高度压低：b树，1个节点1024个值，

图

单元最短路径

当遍历到(3，1), w(0,3)+w (3,1)<w(0,1),更新w(0,1)的值=30，但是这里不能停止，按深度优先的方式，再继续更新下去，因为(0,1)有了更短的路径，1连接出去的所有临界顶点跟0之间可能都会更新出更短的路径，比如w (0，1)+w(1,2) < w(0,2),那么w(0,2)更新为40，以此类推，再往下(0,2)更新出了更短路径，2连接出去所有点，跟0之间可能又有更短路径，还要继续往下更新直到没有更新出更短路径，比如w(0,2)+w(2,4) > w(0,4),没有更新出更短路径，深度遍历的更新就可以停止。遍历所有的边，找出0链接出去的更短路径，但是更过程中只要更新出更短路径，则要深度往边遍历尝试再更新更短的路径。