题解：P1525 [NOIP2010 提高组] 关押罪犯 || 拓展域并查集

这篇文章主要介绍**拓展域并查集**。

拓展域并查集，主要用于一种状态表示无法解决问题的题目。例如本题，一个开关有两种状态，用和不用。

本文主要介绍二倍拓展域的拓展域并查集。

## 什么是拓展域并查集？

拓展域并查集是一种数据结构，用于解决具有多个相互关系集合的问题。它是传统并查集的扩展，能够处理集合间的不同关系，如相互排斥或相互独立的关系。

## 拓展域并查集有什么用？
只看定义是不可以的，我们来看一个应用场景：

$n$ 个点有 $m$ 对关系，把 $n$ 个节点放入**两个集合**里，要求**每对**存在关系的两个节点**不能**放在同一个集合。问能否成功完成？

这个问题我们直接用普通并查集是无法通过的，我们必须换一个更加高级的办法。

在原本的并查集中，$i$ 号点在并查集中对应的点正好为 $i$，而在拓展域并查集中对应的是 $i$ 和 $i+n$ 等。当然这个题只需要 $i$ 和 $i+n$ 就够了，有些需要 $i+2n$ 之类的。

例如：对于以下样例，如果我们使用普通并查集，建出来的图是这样的：

```
4 6
1 2
2 3
3 4
4 5
5 6
6 1
```

![](https://cdn.luogu.com.cn/upload/image_hosting/kefslj3p.png)

但是如果我们对于下面的样例，结果是这样的：

```
4 7
1 2
2 3
3 4
4 5
5 6
6 7
7 1
```

![](https://cdn.luogu.com.cn/upload/image_hosting/frpvpe0i.png)

这张图除了比上面这张多了一个点之外，与上面一张基本没有什么区别，如果我们仅仅只使用并查集的话，是看不出什么区别的。

所以这个使用普通并查集是不可取的。

我们使用拓展域并查集，$u$ 和 $u+n$ 分别表示点 $u$ 的两个相反状态，将 $(u,v+n)$ 连边表示 $(u,v)$ 不应该在一个集合里（也可以看做 $u$ 和 $v$ 的反状态在一个集合里）。当然 $(u,v+n)$ 存在边了，相反地，$(v,u+n)$ 也理应右边。

那么就好办了，判断不可以的方式是存在 $u$ 的正反状态在一个集合里。

附上上面两个样例的图：

![](https://cdn.luogu.com.cn/upload/image_hosting/elgn7s5c.png)

等效图：

![](https://cdn.luogu.com.cn/upload/image_hosting/57800r5i.png)

可以看到这张图明显没有任何 $u$ 的正反状态在一个集合里。

但是第二组的样例就不一样了。

![](https://cdn.luogu.com.cn/upload/image_hosting/126xhjev.png)

不够直观？看看这张等效图：

![](https://cdn.luogu.com.cn/upload/image_hosting/gjnau3e0.png)

可以看出点 $1$ 的正反两个状态在一个集合里，所以不行。

## 拓展域并查集怎么写？

拓展域并查集在写法上仅有初始化与两点连边与普通并查集不同。

初始化：

```
for(int i=1;i<=2*n;i++)fa[i]=i;//2 倍点
```

查询父亲和合并函数与普通并查集一样。

```
int findd(int now){
    if(fa[now]==now)return now;
    return fa[now]=findd(fa[now]);
}
void vnion(int u,int v){
    u=findd(u);v=findd(v);
    if(u==v)return;
    fa[u]=v;
}
```

连边：

```
int u,v;
vnion(u,v+n);
vnion(v,u+n);
```

如果需要集合大小，集合内包含的元素等，直接与普通并查集相同写即可。

## 例题

### P1525 [NOIP2010 提高组] 关押罪犯

[题目传送门。](https://www.luogu.com.cn/problem/P1525)

我们贪心，对影响力从大到小排序。

每遇到一个事件，因为如果让这两个囚犯 $(u,v)$ 在一个监狱内，答案就是这个事件的影响力了。我们尽量尝试让最大影响力发生在后面的时间上，所以我们将 $u$ 与 $v$ 的反状态关在一个监狱里。

当你发现 $u$ 与 $u$ 的反状态关在一个监狱里时，这说明已经没救了，无论如何你都避免不了打架，那么就输出当前影响力即可（显然你可以操控使得影响力最小的事件在一个监狱内发生）。

```
#include<bits/stdc++.h>
using namespace std;
struct node{
	int u,v,w;
}e[100005];
bool cmp(node _,node __){
	return _.w>__.w;
}
int fa[40005];
int findd(int now){
	if(fa[now]==now)return now;
	return fa[now]=findd(fa[now]);
}
void vnion(int u,int v){
	u=findd(u),v=findd(v);
	if(u==v)return;
	fa[u]=v;
}
int n,m;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=2*n;i++)fa[i]=i;
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	}
	sort(e+1,e+m+1,cmp);
	for(int i=1;i<=m;i++){
		vnion(e[i].u+n,e[i].v);
		vnion(e[i].u,e[i].v+n);
		if(findd(e[i].u)==findd(e[i].u+n)||findd(e[i].v)==findd(e[i].v+n)){
			printf("%d",e[i].w);
			return 0;
		}
	}
	printf("0");
	return 0;
}
```

### CF776D The Door Problem

[题目传送门。](https://www.luogu.com.cn/problem/CF776D)

这题最难的是状态设计。也因此这题是蓝。

每个钥匙都有动或不动两种状态，分别设为 $i$ 和 $i+m$。

那么我们对于每个门，看看它初始开不开。设控制它的两把钥匙为 $(u,v)$：

- 如果门初始开，$(u,v)$ 只能同时选或不选，合并 $(u,v)$ 及 $(u+m,v+m)$。
- 如果门初始关，$(u,v)$ 只能二选其一，合并 $(u+m,v)$ 及 $(u,v+m)$。

```
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
vector<int>g[N];
int fa[N],n,a[N],m;
int findd(int now){
    if(fa[now]==now)return now;
    return fa[now]=findd(fa[now]);
}
void vnion(int u,int v){
    u=findd(u);v=findd(v);
    if(u==v)return;
    fa[u]=v;
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=2*m;i++)fa[i]=i;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    for(int i=1,k,x;i<=m;i++){
        scanf("%d",&k);
        for(int j=1;j<=k;j++){
            scanf("%d",&x);
            g[x].push_back(i);
        }
    }
    for(int i=1;i<=n;i++){
        if(a[i]==1){
            vnion(g[i][0],g[i][1]);
            vnion(g[i][0]+m,g[i][1]+m);
        }
        else{
            vnion(g[i][0],g[i][1]+m);
            vnion(g[i][0]+m,g[i][1]);
        }
    }
    for(int i=1;i<=m;i++){
        if(findd(i)==findd(i+m)){
            printf("NO");
            return 0;
        }
    }
    printf("YES");
    return 0;
}
```

正在渲染内容...