带权并查集

简介

带权并查集是一种在维护 $f$ 数组的同时维护一个新数组，代表当前点到根的距离和。

A 两个团伙

题意

告诉你两个操作：

  1. 表示 x y不是同一个团伙
  2. 问你 x y是否是一个团伙

解法

如果两人不是同一团伙，就合并，并且连一条权值为 $1$ 的边，更新点到根的和。

查询就看点到根的距离是否能被 $2$ 整除，能就说明是同一个团伙，否则不是。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
#include <bits/stdc++.h>
using namespace std;

const int N = 1000010;
int f[N],sum[N];
int n,m;
int t;
int find(int x)
{
	if(x==f[x]) return x;
	int root=find(f[x]);
	sum[x]^=sum[f[x]];
	return f[x]=root;
}
int main()
{
	scanf("%d",&t);
	while(t--)
	{
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;i++) f[i]=i,sum[i]=0;
		for(int i=1;i<=m;i++)
		{
			char op;
			int x,y;
			scanf(" %c %d%d",&op,&x,&y);
			int tx=find(x),ty=find(y);
			if(op=='D')
			{
				if(sum[x]^sum[y]) sum[tx]=0;
				else sum[tx]=1;
				f[tx]=ty;
			}
			else
			{
				if(find(x)!=find(y)) puts("Not sure yet.");
				else
				{
					if(sum[x]!=sum[y]) puts("In different gangs.");
					else puts("In the same gang.");
				}
				
			}
		}
	}	
}

B区间和探测

题意

每输入一组数据 l r v 表示区间 l r 之和为 v 。

如果这组数据与前面的数据没有冲突，就统计，否则无视。

问有冲突的数据组数。

思路

这道题的 l r 我们可以转换成 $sum[r] - sum[l-1] = v$ ，同时用带权并查集维护。

那么我们可以维护一个并查集，用每个点到根的距离来判定，比如如果我们要合并 l r ，我们就让他到根的权值 $sum_{x-1},sum_y$ 相减为 $z$。

那么假设我们要合并 $x$，$y$，我们就需要让 $sum_y - sum_{x-1} = z$，假设当前 $y$ 的祖先是 $ty$，那么，$sum_{ty} = sum_x + z - sum_y$，就相当于向 $x-1$ 的祖先 $tx$ 连了一条有权的边，可以使得 $sum_y - sum_{x-1} = z$。

同理，如果发现 $x，y$ 已经合并过了，但 $sum_y - sum_{x-1} \ne z$ ，说明有矛盾了。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
using namespace std;

const int N = 4440010;
int fa[N],sum[N];
int n,m;

int find(int x)
{
	if(x==fa[x]) return x;
	int root=find(fa[x]);
	sum[x]+=sum[fa[x]];
	return fa[x]=root;
}
int main()
{
	scanf("%d%d",&n,&m);
	int ans=0;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		x--;
		int tx=find(x),ty=find(y);
		if(tx==ty && sum[y]-sum[x]!=z) ans++;
		else
		{
			fa[ty]=tx;
			sum[ty]=sum[x]+z-sum[y];
		}
	}
	printf("%d",ans);
}