带权并查集的一些拙见

1635570411782

路径压缩

这是一个普通的并查集。如果我们对 CC 执行find操作,最终会得到 AA ,但是过程中会经过B。如果C的父亲特别多,这步就会消耗相当的时间,我们可以让 CC 直接指向 AA ,省去中间的操作进行优化,下图就是希望得到的结果

1635570596670

操作方法就是 将每个节点直接与其find操作最终得到的节点连接一条边 。在 findfind 方法中实现

1
2
3
4
5
6
7
8
int findx(int x)
{
if(x!=f[x])
{
f[x]=findx(f[x]);
}
return f[x];
}

带权并查集

1635570810836

这就是基于路径压缩的带权并查集的样子。可以看到,在普通并查集的基础上,带权并查集在边中添加了一些额外的信息可以更好的处理问题。在 边上记录额外的信息 的并查集就是 带权并查集

每一条边都记录了节点到根节点的一个权值。基于路径压缩就会产生两个问题:

  • 我们希望得到的是 节点与根节点 的权值。但是在路径压缩之前,每个节点都是与 父节点 连接的,这个权值自然也是和其 父节点 的权值。因此在路径压缩的过程中,权值也应当做出更新。
  • 在两个集团进行合并时,因为两个集团的根节点不同,需要把一个集团的根节点同时赋为另一个集团的根节点。自然也要进行权值的更新

带权并查集のfind

1
2
3
4
5
6
7
8
9
10
11
//value[x]表示节点x到根的权值
int findx(int x)
{
if(x!=f[x])
{
int t=f[x];//记录父亲节点的编号
f[x]=findx(f[x]);
value[x]+=value[t];//父节点已经完成更新了
}
return f[x];
}

先记录下原本父节点的编号,接着路径压缩后父节点就会变成根节点,此时父节点的权值,已经是父节点到根节点的权值了。再加上当前节点与其父节点的权值,就会得到当前节点到根节点的权值

带权并查集のmerge

第一张图是 mergemerge 前,第二张图是 mergemerge

1635572555734

1635572674620

我们需要求出 pxpxpypy 这条边的权值为多少。显然xypyx\rightarrow y\rightarrow pyxpxpyx\rightarrow px\rightarrow py这两条边的权值之和应该相同。容易求出 value[px]=value[y]+tempvalue[x]value[px]=value[y]+temp-value[x] (temp为题目给出的关系)。虽然思想一样,但实际上更新方法都是需要都是参考具体题目的,比如下面要讲的食物链

例题分析:

食物链

动物王国中有三类动物A,B,C,这三类动物的食物链构成了有趣的环形。A吃B, B吃C,C吃A。
现有N个动物,以1-N编号。每个动物都是A,B,C中的一种,但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述:
第一种说法是"1 X Y",表示X和Y是同类。
第二种说法是"2 X Y",表示X吃Y。
此人对N个动物,用上述两种说法,一句接一句地说出K句话,这K句话有的是真的,有的是假的。当一句话满足下列三条之一时,这句话就是假话,否则就是真话。
1) 当前的话与前面的某些真的话冲突,就是假话;
2) 当前的话中X或Y比N大,就是假话;
3) 当前的话表示X吃X,就是假话。
你的任务是根据给定的N(1 <= N <= 50,000)和K句话(0 <= K <= 100,000),输出假话的总数。

在这个题目中,我们需要记录的关系就是食物链上的关系。因此带权并查集的权值为两个动物在食物链上的相对关系。定义ABA \rightarrow B 00 表示为同类,11 表示为A吃B, 22 表示为B吃A

考虑如何更新value?

AB=1,BC=1A \rightarrow B=1,B \rightarrow C=1 ,由题意得 AC=2A \rightarrow C=2

AB=2,BC=2A \rightarrow B=2,B \rightarrow C=2 ,由题意得 AC=1A \rightarrow C=1

AB=0,BC=1A \rightarrow B=0,B \rightarrow C=1 ,由题意得 AC=1A \rightarrow C=1

AB=1,BC=2A \rightarrow B=1,B \rightarrow C=2 ,由题意得 AC=0A \rightarrow C=0

……

应该可以看出来 AC=(AB+BC)mod3A \rightarrow C=(A \rightarrow B + B \rightarrow C) mod 3

考虑如何进行区间合并?

和我们最开始的板子相比,这道题就多了一个取模的操作,因此区间合并时加一句取模就行了

考虑如何判断矛盾?

已知 AA 与根节点的关系,已知 BB 与根节点的关系,这些都是自己通过并查集维护的。我们已经知道如何求出 ABA \rightarrow B 的关系,当 AABB 是同一个根节点时只要我们求出的关系与题目给出的关系 不同 即可说明存在矛盾。如果 AABB 不是同一个根节点,我们就维护并查集。

1635575514008

(val1val2+3)mod3==temp(val1-val2+3)mod3==temp ???

Warning!!!

题目只给出了1和2两种关系,0 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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include<iostream>
using namespace std;
#define ll long long
#define MAXN 50005
ll n,m;
ll f[MAXN];ll val[MAXN];
ll temp;
ll ans;
int findx(int x)
{
if(x!=f[x])
{
int t=f[x];
f[x]=findx(f[x]);
val[x]=(val[x]+val[t])%3;
}
return f[x];
}

void merge(int x,int y)
{
int fx=findx(x);
int fy=findx(y);
if(fx==fy)
{
if(temp!=(val[y]-val[x]+3)%3)
ans++;
}
else
{
f[fy]=fx;
val[fy]=(val[x]+temp-val[y])%3;
}
}

void solve()
{
cin>>n>>m;
for(int i=1;i<=n;i++) f[i]=i;
for(int i=1;i<=m;i++)
{
ll u,v;
cin>>temp>>u>>v;
if(u>n||v>n||(temp==2&&u==v))
{
ans++;
continue;
}
if(temp==1) temp=0;//相同
else if(temp==2) temp=1;//A吃B
merge(u,v);
}
cout<<ans<<endl;
}

int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
solve();
return 0;
}

1635579105881

完完全全的模板题 传送

题意:

求在有 nn 个数中,有 mm 次询问,每次询问在这给定的区间和这区间里数的和为 sumsum ,求每次给出的是不是正确的 sumsum 。也就是和前面的矛盾不矛盾。

考虑如何判断矛盾?

假设有两个线段 ABAC (B>C) ,他们有共同的起点,已知 ABAC 的长度。现在给出 CB 的长度,如果 ABACCBAB-AC \neq CB 即为出现了矛盾

考虑如何维护并查集?

定义一个点的根为他能到达的最左端的端点。维护的 valval 是这个节点和最左端节点的距离。

1635580976789

temp=val1val2temp=val1-val2

1635581844480

???=val[x]+tempval[y]???=val[x]+temp-val[y]

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 200005
int f[MAXN];
ll val[MAXN];
ll n, m;
ll ans = 0;
int findx(int x)
{
if (f[x] != x)
{
int t = f[x];
f[x] = findx(f[x]);
val[x] += val[t];
}
return f[x];
}

void merge(int x, int y, ll temp) //x<y
{
int fx = findx(x); //类似于前缀和,要减去1
int fy = findx(y);
if (fx == fy) //判断有没有矛盾
{
if (val[x] + temp != val[y])
{
ans++;
return;
}
}
else if (fx < fy)
{
f[fy] = fx;
val[fy] = val[x] + temp - val[y];
}
else if (fy < fx)
{
f[fx] = fy;
val[fx] = val[y] - temp - val[x];
}
int valfx, valfy;
valfx = val[fx];
valfy = val[fy];
}

void solve()
{
while (cin >> n >> m)
{
for (int i = 0; i <= n; i++)
f[i] = i;
for (int i = 0; i <= n; i++)
val[i] = 0;
ans = 0;
for (int i = 1; i <= m; i++)
{
int u, v;
ll temp;
cin >> u >> v >> temp;
merge(u - 1, v, temp);
}
cout << ans << endl;
}
}

int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
return 0;
}

然后是你最喜欢的CF

题意:

给出一些 nn 个单词,给出 mm 个关系:单词 uu 和单词 vv同义词反义词 。如果这些关系和 之前 给出的关系出现了 矛盾 ,输出NO,否则输出YES

再给出 qq 组询问,询问单词 uuvv 的关系,有且仅有以下

  • 同义词
  • 反义词
  • 毫无关系

思路:

同义词和反义词,emm,先写写看看

同义词的同义词是同义词

反义词的反义词是同义词

同义词的反义词是反义词

反义词的同义词是反义词

是不是有点像 01模数 ,分别对应

(0+0)mod2=0(0+0) mod 2 = 0

(1+1)mod2=0(1+1)mod2=0

(1+0)mod2=1(1+0)mod2=1

(0+1)mod2=1(0+1)mod2=1

考虑如何更新value?

上面已经给出了过程,同义词对应(val[x]+val[y])mod2(val[x]+val[y]) mod2 ,反义词对应(val[x]+val[y]+1)mod2(val[x]+val[y]+1)mod2

考虑如何维护集团?

每有一条连边就加进来,集团内的成员元素只有两种关系,同义词或反义词

1635593939569

  • 同义词 (val[x]+val[y])mod2(val[x]+val[y])mod2
  • 反义词 (val[x]+val[y]+1)mod2(val[x]+val[y]+1)mod2

考虑如何判断关系?

  • 同一集团且不相等,反义词
  • 同一集团且相等,同义词
  • 非同一集团,非相关

考虑如何判断矛盾?

  • 给出的关系是相反但是两个单词位于同一集团且值相等
  • 给出的关系是相同但是两个单词位于同一集团且值不同

其他技巧:用map来映射字符串,这样可以正常的访问和使用并查集

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define MAXN 100005
ll n,m,q;
string s,v,u;
map <string,int> mp;//用int来映射字符串
int f[MAXN];
int val[MAXN];//对每个集团内的字符串通过0和1赋值来表示是不是近义词,反义词
//同义词的同义词是同义词 (0+0)%2
//反义词的反义词是同义词 (1+1)%2
int findx(int x)
{
if(f[x]!=x)
{
int t=f[x];
f[x]=findx(f[x]);
val[x]=(val[x]+val[t])%2;
}
return f[x];
}

void solve()
{
cin>>n>>m>>q;
for(int i=1;i<=n;i++)
{
cin>>s;
mp[s]=i;//对字符串映射,这样就能通过正常的并查集访问了
f[i]=i;
val[i]=0;//开始默认所有词都是同义词(不是同一集团,没事)
}
int flag;
while(m--)
{
cin>>flag>>u>>v;
int x=mp[u];int y=mp[v];
if(flag==1)//同义词
{
if(findx(x)==findx(y)&&val[x]!=val[y])//非法情况
{
cout<<"NO"<<endl;
continue;
}
else//维护并查集
{
cout<<"YES"<<endl;
int fx=findx(x);
int fy=findx(y);
f[fy]=fx;//这题难得顺序无所谓
val[fy]=(val[x]+val[y])%2;
}
}
else//反义词
{
if(findx(x)==findx(y)&&val[x]==val[y])//非法情况
{
cout<<"NO"<<endl;
continue;
}
else//维护并查集
{
cout<<"YES"<<endl;
int fx=findx(x);
int fy=findx(y);
f[fy]=fx;
val[fy]=(val[x]+val[y]+1)%2;
}
}
}
while(q--)
{
cin>>u>>v;
int x=mp[u];int y=mp[v];
if(findx(x)==findx(y)&&val[x]!=val[y]) cout<<2<<endl;
else if(findx(x)==findx(y)&&val[x]==val[y]) cout<<1<<endl;
else if(findx(x)!=findx(y)) cout<<3<<endl;
}
}

int main()
{
ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
solve();

return 0;
}

总结:

其实模板就那样,主要是思考如何维护并查集的过程。遇到判断矛盾的时候就可以想到带权并查集了。如何定义根节点?每个节点到根的value是什么?如何更新每个节点到根的value?矛盾形成的条件是什么?在区间合并的时候如何保证两条路径上的边权和相同?

我相信如果能熟练的想起这些思路,并快速应用于具体题目,这类题目就拿下了~~(很明显我没有)~~