蓝桥杯之并查集

算法思想

并查集是一种树形的数据结构，主要用于解决一些元素分组问题。用于处理一些不相交集合的合并以及查询问题。并查集的思想是用一个数组表示了整片森林，树的根节点唯一标识了一个集合，我们只要找到了某个元素的树根，就能确定他在哪个集合里

问题场景：

合并：将若干个元素合并到一个或者多个集合（构成一棵

树或多棵树），将多个集合合并（多棵树合并为一棵树），合并x，y两个元素时，不能直接合并两个元素，而是要合并两个元素所在的树根

查询：查询两个元素是否在同一个集合中。查询x和y是否在同一个集合，查找x和y对应的树根，看看是否是同一个树的树根

其他：计算共有几个集合（几棵树）

代码实现：

//并查集,(查找两个数字在不在一个集合中)
const int Size = 9;//（数字范围为1-8)，在parent数组中下标就可以来表示数字，下标对应的值
//就可以来指向其父节点
int parent[Size];
//加权优化,规定节点层数，每次放节点时从节点层数高的放
int Rank[Size];
//加权优化与路径压缩只能存在一个，因为路径压缩会改变Rank值
//找x对应的父节点
int find(int x)
{
	if (x == parent[x])
	{
		return x;
	}
	//路径压缩：在将每一个的值得父节点都改为最终的父节点
	//parent[x]= find(parent[x]);
	//return parent[x];
	return find(parent[x]);
}
//合并就是去合并根节点
void merge(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x != y)
	{
		if (Rank[x] > Rank[y])
		{
			parent[y] = x;
		}
		else if (Rank[x] < Rank[y])
		{
			parent[x] = y;
		}
		else
		{
			parent[y] = x;
			Rank[x]++;
		}
	}
}
int main()
{
	for (int i = 0; i < Size; i++)
	{
		//刚开始默认父节点为自己
		parent[i] = i;
		Rank[i] = 1;
	}
	int x, y;
	for (int i = 0; i < 6; i++)
	{
		cin >> x >> y;
		merge(x, y);
	}
	cout << (find(6)==find(1))?"ok":"no";
	return 0;
}

例子：最小生成树

现在有一个地点为Ai，一个地点为Bi，又一个结构为一条路，这条路连接（存储）了两个地点，还有到这两个地点的距离cost，一个Ai一个Bi一个cost构成了一个最小集合，现在有n个这样的集合，

那么可以根据这个cost，比如现在根据cost来将n个最小集合排序，现在问一个Ai到Bj之间怎么怎么样，那Ai与Bj肯定是要相互连通的，根据上面的并查集结构，将这n个最小集合构成一个并查集所形成的的树就叫最小生成树，如果Ai与Bj有公共父节点那么他们肯定是连通的，这时可以根据题目要求结合下面的代码进行求解（比如问题：躲避拥堵的最佳路线）

struct Edge
{
	Edge(int s, int e, int c) :start(s), end(e), cost(c)
	{

	}
	int start;
	int end;
	int cost;
};
int parent[10000];
int find(int x)
{
	if (x == parent[x])
	{
		return x;
	}
	return parent[x] = find(parent[x]);
}
bool Mycompare(const Edge& e1, const Edge& e2)
{
	return e1.cost < e2.cost;
}
int main()
{
	for (int i = 0; i < 10000; i++)
	{
		parent[i] = i;
	}
	vector<Edge>edge;
	int n;
	cin >> n;
	char s, e;
	int c;
	for (int i = 0; i < n; i++)
	{
		cin >> s >> e >> c;
		edge.push_back(Edge(s, e, c));
	}
	sort(edge.begin(), edge.end(), Mycompare);
	for (int j = 0; j < edge.size(); j++)
	{
		int a = find(edge[j].start);
		int b = find(edge[j].end);
		if (a != b)
		{
			parent[a] = b;
			printf("%c->%c:cost:%d ", edge[j].start, edge[j].end, edge[j].cost);
		}
		
	}
	return 0;
}