并查集
序言:我们大家都是好朋友
并查集是一种维护关系的数据结构
新手所学的并查集都是维护朋友关系的并查集
朋友的朋友是朋友
我们可以将变成朋友的点连到同一个集合中
模板
//并查集
const int N=2e5+10;
int p[N];
int find(int x){
if(p[x]!=x)p[x]=find(p[x]);
return p[x];
}
蒙尘:你讨厌我我也讨厌你
一般的并查集只能够维护朋友关系
但是有些题目需要维护敌人关系
此时有
敌人的敌人是朋友
根据这条属性,我们可以将并查集拓展
使其能够维护敌人关系
我们可以单独开辟出两个集合
如果 \(a\) 和 \(b\) 是敌人,那么就将 \(a\) 和 \(b+n\) 将 \(a+n\) 和 \(b\) 合并到一个集合中
如果 \(a\) 和 \(c\) 是敌人,那么就将 \(a\) 和 \(c+n\) 将 \(a+n\) 和 \(c\) 合并到一个集合中
那么我们可以发现
\(b\) 和 \(c\) , \(b+n\) 和 \(c+n\) 都合并到一个集合中了
由此便实现了敌人的敌人是朋友的属性
终章:原来你一直讨厌我吗
上面讲的敌人的属性是建立在敌对关系是双向的基础上
那如果敌对关系是单向的呢
那就要开三个集合
考虑在不同种类的并查集中合并的意义,表达了 他们是敌人 这个关系
具体实现请类比蒙尘篇
例题:P2024[NOI2001]食物链https://www.luogu.com.cn/problem/P2024)
标签:关系,朋友,查集,int,集合,敌人 From: https://www.cnblogs.com/liangqianxing/p/17145558.html