带权并查集题解

PS：题解参考了许多dalao的文章所以难免有既视感，请见谅

一般普通的并查集只能确定节点与父节点的关系，但比如像是食物链这种类型的题目，给定了ABC的关系，这个时候就需要给并查集加权，这个权一般用来表示两个节点之间的关系，由于三种动物之间是吃与被吃的关系，所以我们不妨用模运算来表示节点之间的关系。

1.权值确定

0-节点与父节点是同类 1-节点被父节点吃 2-节点吃父节点这样定义关系以后正好可以与题目中输入1-x与y同类 2-x吃y相对应。

2.节点关系确定

节点间的关系

首先我们定义两个两个数组fa[],rank[]，fa用来维护并查集，而rank则是用来表示当前节点与父节点的关系。

下面我们通过穷举推导出通过AB关系表示一节点与父节点关系的关系式。

节点A与父关系	节点A与B关系	节点B与父关系
0	0	0
0	1	1
0	2	2
1	0	1
1	1	2
1	2	0
2	0	2
2	1	0
2	2	1
由此不难得出关系式:rank[B]=(rank[B]+rank[A])%3这个公式可以用来更新并查集

这样就可以通过节点与之前父节点的关系和之前父节点到当前节点的关系来维护当前节点与现在父节点的关系

集合间的关系

我们可以通过当前节点的关系反推出两集合间的关系。两集合分别是X所在集合和Y所在集合，设A=findx(X),B=findx(Y),首先我们来看一下推导出的公式 :（p为判断XY是同类还是互吃）

rank[A]=(rank[X]-rank[Y]+3+(p-1))%3

p-1：这是XY之间的关系， 3-rank[Y]:父节点与Y的关系

所以两集合合并的过程是这样的：先把X与Y相关联，这样X是Y的父亲，那原来Y的父亲便变成了Y的子节点，再把Y的父节点与X关联，最后把Y的父节点从X移动到X的父节点上，通过之前的关系式rank[B]=(rank[B]+rank[A])%3不难推导：

Y与现在父节点X的关系	+	Y原来父节点与Y的关系
p-1	+	3-rank[Y]

这便是Y父节点与X的关系，之后再加上X与X父节点的关系，就不难得到两集合合并的关系式了，不妨自己举几个例子来验证正确性。

3.判断真假

要想证明是否正确的，首先要把两个元素合并到同一集合中，假如两个元素不在同一集合的话，除非违背了规则，否则就是真的我们可以通过之前推导的公式来进行判断

首先判断1 x y是不是假

1
2
3
4
5
6


int a=findx(x),b=findx(y);
if(a==b)
	{
	if(d==1)
    if(rank[x]!=rank[y]) return false;
    }

然后判断2 x y是不是假

1
2
3


if(d==2)
if((3-rank[x]+rank[y])%3!=2) return false;
//通过公式计算出两个元素之间是不是吃与被吃关系

4.AC代码

 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
47


#include<bits/stdc++.h> //万能头 
using namespace std;
const int maxn=200000;
int n,m,fa[maxn],rank[maxn],ans=0;//定义见上文 
int findx(int x) //建立并查集 
{
	if(x==fa[x]) return fa[x];
	int t=fa[x]; //获取x的父节点 
	fa[x]=findx(fa[x]);
	rank[x]=(rank[x]+rank[t])%3;
	return fa[x];
}
bool pan(int d,int x,int y)
{
	int a=findx(x),b=findx(y);
	if(a==b)
	{
		if(d==1)
			if(rank[x]!=rank[y]) return false;
		if(d==2)
			if((3-rank[x]+rank[y])%3!=2) return false;
	}
	fa[a]=b;
	if(d==1)
	rank[a]=(3+rank[y]-rank[x])%3;
	else 
	rank[a]=(3+1+rank[y]-rank[x])%3;
	return true;
} 
int main()
{
	int d,x,y;
	cin>>n>>m;
	for(int i=1;i<=n;i++) fa[i]=i;
    for(int i=1;i<=m;i++)
    {
    	cin>>d>>x>>y;
    	if(x>n||y>n||(d==2&&x==y))//筛选情况 
    	{
    		ans++;
    		continue;
		}
		if(!pan(d,x,y)) ans++;
	}
	cout<<ans<<endl;
	return 0;
}

P2024 食物链