并查集扩展
目录普通并查集
例题:
1.洛谷P1197 星球大战
链接:
[P1197 JSOI2008] 星球大战 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
类型:
普通并查集+反向加点
解析:
正面删边很难,考虑反向求解,先求删完所有要求点的所有连通块数量,然后再一个一个加入,将问题简化
代码:
const int N = 400005;
struct edges{
int v,ne;
}e[N << 1];
int h[N],idx = 0;
void add(int u,int v){
e[idx] = {v,h[u]};
h[u] = idx++;
}
int f[N];
int fd(int x){
if(x==f[x]) return x;
return f[x] = fd(f[x]);
}
int vis[N],ans[N];
int n,m;
void solve(){
memset(h,-1,sizeof h);
cin >> n >> m;
for(int i = 1;i<=n;i++) f[i] = i;
vector<int> b;
for(int i = 1;i<=m;i++){
int u,v;
cin >> u >> v;
u++,v++;
add(v,u);
add(u,v);
}
int k;
cin >> k;
int res = n - k;
for(int i = 0;i<k;i++){
int t;
cin >> t;
t++;
vis[t] = 1;
b.push_back(t);
}
for(int i = 1;i<=n;i++){
if(vis[i]) continue;
for(int j = h[i];~j;j=e[j].ne){
int v = e[j].v;
if(vis[v]) continue;
if(f[fd(i)] != f[fd(v)]){
res--;
f[fd(i)] = f[fd(v)];
}
}
}
ans[k+1] = res;
for(int i = k - 1;i >= 0;i--){
vis[b[i]] = 0;
res++;
for(int j = h[b[i]];~j;j=e[j].ne){
int v = e[j].v;
if(vis[v]) continue;
if(f[fd(b[i])] != f[fd(v)]){
res--;
f[fd(b[i])] = f[fd(v)];
}
}
ans[i + 1] = res;
}
for(int i = 1;i<=k+1;i++){
cout << ans[i] << endl;
}
}
2.洛谷P1955 程序自动分析
链接:
[P1955 NOI2015] 程序自动分析 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
类型:
普通并查集+离散化
解析:
普通并查集判断是否矛盾,数据大进行离散化
代码:
const int N = 200005;
struct DSU {
vector<int> f;
DSU(){}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
iota(f.begin(), f.end(), 0);
}
int fd(int x) {
if(f[x]==x) return x;
return f[x] = fd(f[x]);
}
bool same(int x, int y) {
return fd(x) == fd(y);
}
bool mg(int x, int y) {
x = fd(x);
y = fd(y);
if (x == y)return false;
f[y] = x;
return true;
}
};
int gt_idx(vector<int>& a,int i){
int t = lower_bound(a.begin(),a.end(),i) - a.begin() + 1;
return t;
}
void solve(){
int n;
cin >> n;
vector<int> v1;
vector<pair<int,int>> ys;
vector<pair<int,int>> ns;
vector<int> a;
for(int i = 0;i < n;i++){
int u,v,op;
cin >> u >> v >> op;
if(op==1){
ys.push_back({u,v});
}else{
ns.push_back({u,v});
}
a.push_back(u);
a.push_back(v);
}
sort(a.begin(),a.end());
a.erase(unique(a.begin(),a.end()),a.end());
int sz = a.size();
DSU d(sz + 1);
for(auto &[u,v]:ys){
d.mg(gt_idx(a,u),gt_idx(a,v));
}
for(auto &[u,v]:ns){
if(d.fd(gt_idx(a,u)) == d.fd(gt_idx(a,v))){
cout << "NO" << endl;
return;
}
}
cout << "YES" << endl;
}
带权并查集
例题:
1.洛谷P2024 食物链
链接:
[P2024 NOI2001] 食物链 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
类型:
带权并查集
解析:
维护%3关系,考虑合并时候维护集合关系,在同类时候d[u] - d[v]在%3意义下一定是0,x吃y那么一定是1,题目无需考虑2的情况,因为没有设置y吃x的正确性
代码:
const int N = 200005;
int f[N],d[N];
int n,m;
int fd(int x){
if(x!=f[x]){
int t = f[x];
f[x] = fd(f[x]);
d[x] += d[t];
}
return f[x];
}
int calc(int x,int y){
return ((x-y)%3 + 3)%3;
}
void merge(int x,int y,int v){
int px = fd(x),py = fd(y);
f[px] = py;
d[px] = d[y] - d[x] + v;
}
void solve(){
cin >> n >> m;
iota(f,f+n+1,0);
int cnt = 0;
while(m--){
int u,v,op;
cin >> op >> u >> v;
if(u>n||v>n){
cnt++;
continue;
}
if(op==1){
if(fd(u)==fd(v) && calc(d[u],d[v]) != 0){
cnt++;
continue;
}
//d[v] = d[u] + d[fd(u)]
//d[fd[u]] = d[v] - d[u]
if(fd(u)!=fd(v)) merge(u,v,0);
}else{
if(fd(u)==fd(v) && calc(d[u],d[v]) != 1){
cnt++;
continue;
}
//d[v] = d[u] - 1 + d[fd(u)]
//d[fd[u]] = d[v] - d[u] + 1
if(fd(u)!=fd(v)) merge(u,v,1);
}
}
cout << cnt << endl;
}
2.洛谷P1196 银河英雄传说
链接:
[P1196 NOI2002] 银河英雄传说 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
类型:
带权并查集
解析:
维护两个变量,一个是集合大小,一个是元素到根的距离,然后操作即可
代码:
const int N = 200005;
int sz[N],d[N],f[N];
void init(){
for(int i = 0; i < N - 1;i++){
f[i] = i;
sz[i] = 1;
}
}
int fd(int x){
if(f[x]!=x){
int t = f[x];
f[x] = fd(f[x]);
d[x] += d[t];
}
return f[x];
}
void merge(int x,int y){
int px = fd(x),py = fd(y);
f[px] = py;
d[px] = sz[py];
sz[py] += sz[px];
}
void solve(){
int q;
init();
cin >> q;
while(q--){
int x,y;
char op;
cin >> op >>x >> y;
if(op=='C'){
if(fd(x)!=fd(y)){
cout <<-1<<endl;
}else{
cout << abs(d[x]-d[y]) - 1 << endl;
}
}else{
merge(x,y);
}
}
}
3.洛谷P5937 Parity Game
链接:
[P5937 CEOI1999] Parity Game - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
类型:
带权并查集
解析:
前缀和思想,合并 y 与 x - 1 判断奇偶性即可
代码:
const int N = 200005;
int n,q;
int idx = 0;
map<int,int> h;
int gt(int x){
if(h.count(x)) return h[x];
h[x] = ++idx;
return idx;
}
int d[N],f[N];
int fd(int x){
if(f[x] != x){
int t = f[x];
f[x] = fd(f[x]);
d[x] += d[t];
}
return f[x];
}
void merge(int x,int y,int v){
int px = fd(x),py = fd(y);
f[px] = py;
d[px] = d[y] - d[x] + v;
}
int calc(int x,int y){
return ((d[x] - d[y])%2 + 2)%2;
}
void solve(){
cin >> n >> q;
int res = q;
for(int i = 0;i<N;i++) f[i] = i;
int id = 0;
while(q--){
int x,y;
++id;
string op;
cin >> x >> y >> op;
if(x==y&&op=="even"){
res = id-1;
break;
}
x = gt(x - 1);
y = gt(y);
if(op=="even"){
if(fd(x)==fd(y)){
if(calc(x,y) == 1){
res = id - 1;
break;
}
}else{
merge(x,y,0);
}
}else{
if(fd(x)==fd(y)){
if(calc(x,y) == 0){
res = id - 1;
break;
}
}else{
merge(x,y,1);
}
}
}
cout << res << endl;
}
扩展域并查集
例题:
1.洛谷P1525 关押罪犯
链接:
[P1525 NOIP2010 提高组] 关押罪犯 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
类型:
扩展域并查集 + 带权并查集
解析:
方法一(扩展域并查集):
- 两个集合,从大到小排序,考虑将敌对两个人分成两个集合,并且扩展域合并,敌人的敌人是朋友,就是设x有两个敌人 y z, 那么 z 与 x+n 建边, x +n 与 y 建边,通过 x+n这个虚点去连接应该在一个集合中的y与z,如果在同一集合,并且是敌对,那么直接输出即可
方法二(带权并查集):
- 从大到小排序,避免前面的数在一个监狱,将两个集合合并起来,并且赋权值为1代表两个数不在同一监狱,于是在后面我们可以判断,如果两个数之前已经合并过并且mod操作位0代表,这两个集合一定要在一个监狱中,那么直接输出w,(否则,w会更大)
代码:
方法一:
int n,m;
struct qs{
int u,v,w;
bool operator<(const qs& q1)const{
return w > q1.w;
}
};
struct DSU {
vector<int> f, sz;
DSU(){}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
iota(f.begin(), f.end(), 0);
sz.assign(n, 1);
}
int fd(int x) {
if(f[x]==x) return x;
return f[x] = fd(f[x]);
}
bool mg(int x, int y) {
x = fd(x);
y = fd(y);
if (x == y)return false;
f[y] = x;
return true;
}
};
void solve(){
cin >> n >> m;
DSU d(2*(n+1));
vector<qs> q;
for(int i = 0; i < m;i++){
int u,v,w;
cin >> u >> v >> w;
q.push_back({u,v,w});
}
sort(q.begin(),q.end());
for(int i = 0;i < q.size();i++){
int u = q[i].u,v = q[i].v,w = q[i].w;
if(d.fd(u) == d.fd(v)){
cout << w <<endl;
return;
}
d.mg(u,v+n);
d.mg(u+n,v);
}
cout << 0 << endl;
}
方法二:
struct qs
{
int u,v,w;
bool operator<(const qs &t)const{return w > t.w;};
};
int f[N],d[N];
int n,m;
int fd(int x){
if(x!=f[x]){
int t = f[x];
f[x] = fd(f[x]);
d[x] += d[t];
}
return f[x];
}
int calc(int x,int y){
return ((x-y)%2 + 2)%2;
}
void merge(int x,int y){
int px = fd(x),py = fd(y);
f[px] = py;
d[px] = d[y] - d[x] + 1;
}
void solve(){
cin >> n >> m;
int q = m;
vector<qs> a;
iota(f,f+n+1,0);
while(q--){
int u,v,w;
cin >> u >> v >> w;
a.push_back({u,v,w});
}
sort(a.begin(),a.end());
for(int i = 0; i < m;i++){
int u = a[i].u,v = a[i].v,w = a[i].w;
if(fd(u)==fd(v)){
if(calc(d[u],d[v]) == 0){
cout << w << endl;
return;
}
}else{
merge(u,v);
}
}
cout << 0 <<endl;
}