带权并查集

转载自一个大佬的文章：原文章
作者：syddf_shadow

带权并查集需要先理解一般的并查集，不明白的可自行先搜索有关内容

一般的并查集主要记录节点之间的链接关系，而没有其他的具体的信息，仅仅代表某个节点与其父节点之间存在联系，它多用来判断图的连通性，如下图所示，这是一个并查集，其中箭头表示父子关系，可以看到这些边没有记录其他的任何信息。

而有的时候在这些边中添加一些额外的信息可以更好的处理需要解决的问题，在每条边中记录额外的信息的并查集就是带权并查集。
不过在此之前先来看看并查集的路径压缩：
在上边这个并查集中，如果对节点C做Find操作，最终会得到A，但是查找的过程中会先经过B，再通过Find(B)得到A，这是一个值得优化的地方，如果直接让C链接到A不是更好吗，这样就可以省去中间的操作，如果C跟A直接相隔很多节点，这个优化就极大地提升了查找的效率，也就是希望得到这样的结果：
带权并查集
将每个节点直接与其Find()操作最终得到的节点链接，就是所谓的路径压缩，这一操作可以直接在Find中完成，看下边的代码：

int find(int x)
{
	if (x != parent[x])
	{
		parent[x] = find(parent[x]);
	}
	return parent[x];
}

与一般的并查集相比，它只是在find(parent[x])前边加了一步赋值操作，将在查找过程中遇到的所有的节点的父节点都设为最终得到的那个节点。
基于路径压缩，带权并查集就是：

可以看到它的每一条边都记录了每个节点到根节点的一个权值，这个权值该设为什么由具体的问题而定，一般都是两个节点之间的某一种相对的关系，但是考虑到权值就会有两个问题：

1.每个节点都记录的是与根节点之间的权值，那么在Find的路径压缩过程中，权值也应该做相应的更新，因为在路径压缩之前，每个节点都是与其父节点链接着，那个Value自然也是与其父节点之间的权值

2.在两个并查集做合并的时候，权值也要做相应的更新，因为两个并查集的根节点不同。

下面就来看在这两个过程中，如何更新权值：
路径压缩：

int find(int x)
{
	if (x != parent[x])
	{
		int t = parent[x];
		parent[x] = find(parent[x]);
		value[x] += value[t];
	}
	return parent[x];
}

可以看到更新权值只多了两行代码，先记录下原本父节点的编号，因为在路径压缩后父节点就变为根节点了，再将当前节点的权值加上原本父节点的权值，此时父节点的权值已经是父节点到根节点的权值了，因此加上这个权值就会得到当前节点到根节点的权值。
合并：

		int px = find(x);
		int py = find(y);
		if (px != py)
		{
			parent[px] = py;
			value[px] = -value[x] + value[y] + s;
		}

现在是已知x所在的并查集根节点为px，y所在的并查集根节点为py，如果有了x、y之间的关系，要将px并到py上，如果不考虑权值直接修改parent就行了，但是现在是带权并查集，必须得求出px与py这条边的权值是多少，很显然x到py两条路径的权值之和应该相同，就不难得出上面代码所表达的更新式。但是需要注意并不是每个问题都是这样更新的，有时候可能会做取模之类的操作，这一点在后边的例题中可以体现。
以上便是带权并查集所需要理解的操作，下面来看三个具体的例子：
HDU-3038-How Many Answers Are Wrong
这个题题目的废话比较多，这里简述一下大意：有M个数，不知道它们具体的值，但是知道某两个数之间（包括这两个数）的所有数之和，现在给出N个这样的区间和信息，需要判断有多少个这样的区间和与前边已知的区间和存在矛盾。例如给出区间和[1,4]为20，[3,4]为15，再给出[1,2]为30，显然这个[1,2]的值就有问题，它应该为20-15=5。
这个题目需要分析什么时候会产生矛盾，不妨就具体看看上面的这个矛盾的例子
带权并查集
在这里这个图是画不了的，因为使用的都是闭区间，闭区间会加上端点的值，这就提醒我们这个题在处理的时候应该将闭区间的某一端变成开区间，比如将[1,4]变成(0,4]，将[3,4]变成(2,4]，将[1,2]变成(0,2]

如果已知(2,4]，(0,4]，那么(0,2]的值就可以求出来，如果说再给出(0,2]的值，而又不与(0,2]求出来的值相等，就产生了矛盾，这是矛盾产生的唯一情况：某个区间的值可以由前边的区间求出来，而又给出了这个区间错误的值。注意，有的地方对这个题的分析存在很大的误解，有的博客中说如果已知[1,10]为100，[1,5]为1000，[1,5]的值不可能大于100所以矛盾，这是不对的，因为本题题目中没有说所有的数都是正数，因此矛盾只有在不相等的时候产生。
带权并查集
那么需要考虑什么时候一个区间的值可以由之前的区间求出来呢？观察上边这张图，红色的这条边是求不出来的，而绿色的是可以求出来的，为什么呢？因为0、2属于同一个并查集，0、3不属于同一个并查集，因此不难得出本题的求解思路：如果给定区间的两个端点属于同一个并查集，判断这个区间的值是否与计算得到的值相等；如果给定区间的两个端点不属于同一个并查集，将这两个并查集合并。并查集边的权值就等于题干中的区间和。

#define _CRT_SECURE_NO_WARNINGS
 
#include <iostream>
#include <stdio.h>
using namespace std;
 
const int maxM = 200005;
int parent[maxM];
int sum[maxM];
 
int Find(int x)
{
	if (x != parent[x])
	{
		int i = parent[x];
		parent[x] = Find(parent[x]);
		sum[x] += sum[i];
	}
	return parent[x];
}
 
 
int main()
{
	int m, n;
	int ans = 0;
	while (scanf("%d%d", &m, &n) != EOF)
	{
		for (int i = 0; i <= m; i++)
		{
			parent[i] = i;
			sum[i] = 0;
		}
		ans = 0;
		while (n--)
		{
			int l, r, value;
			cin >> l >> r >> value;
			l--;
			int fl = Find(l);
			int fr = Find(r);
			if (fl == fr)
			{
				if ((sum[l] - sum[r]) != value)
				{
					ans++;
				}
			}
			else {
				parent[fl] = fr;
				sum[fl] = -sum[l] + sum[r] + value;
			}
		}
		cout << ans << endl;
	}
	return 0;
}

由此可见带权并查集实际上就类似于前缀和，通过已知的两个相对信息求出一个绝对信息。

HihoCoder-1515-分数调查
描述
小Hi的学校总共有N名学生，编号1-N。学校刚刚进行了一场全校的古诗文水平测验。

学校没有公布测验的成绩，所以小Hi只能得到一些小道消息，例如X号同学的分数比Y号同学的分数高S分。

小Hi想知道利用这些消息，能不能判断出某两位同学之间的分数高低？

输入
第一行包含三个整数N, M和Q。N表示学生总数，M表示小Hi知道消息的总数，Q表示小Hi想询问的数量。

以下M行每行三个整数，X, Y和S。表示X号同学的分数比Y号同学的分数高S分。

以下Q行每行两个整数，X和Y。表示小Hi想知道X号同学的分数比Y号同学的分数高几分。

对于50%的数据，1 <= N, M, Q <= 1000

对于100%的数据，1 <= N, M, Q<= 100000 1 <= X, Y <= N -1000 <= S <= 1000

数据保证没有矛盾。

输出
对于每个询问，如果不能判断出X比Y高几分输出-1。否则输出X比Y高的分数。

样例输入

10 5 3
1 2 10
2 3 10
4 5 -10
5 6 -10
2 5 10
1 10
1 5
3 5
样例输出

-1
20
0
这道题给的都是相对关系，显然可以用带权并查集来做，权值就是子节点比父节点多的分数，询问能求解的情况就是两个人同属于一个并查集的情况。这里不多解释了：

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
const int maxN = 100005;
int parent[maxN];
int score[maxN];
 
int find(int x)
{
	if (x != parent[x])
	{
		int t = parent[x];
		parent[x] = find(parent[x]);
		score[x] += score[t];
	}
	return parent[x];
}
int main()
{
	int n, m, q;
	scanf("%d%d%d", &n, &m, &q);
	for (int i = 1 ; i <= n ; i ++ )
	{
		parent[i] = i;
	}
	while ( m-- )
	{
		int x, y, s;
		scanf("%d%d%d", &x, &y, &s);
		int px = find(x);
		int py = find(y);
		if (px != py)
		{
			parent[px] = py;
			score[px] = -score[x] + score[y] + s;
		}
	}
	while ( q -- )
	{
		int x, y;
		scanf("%d%d",&x,&y);
		if (find(x) != find(y))
		{
			printf("-1\n");
		}
		else {
			printf("%d\n", score[x] - score[y]);
		}
	}
	
	return 0;
}

带权并查集

带权并查集

相关推荐