【并查集】扩展域带边权离散化

Genevieve_xiao

214人浏览 · 2021-10-23 11:53:35

Genevieve_xiao · 2021-10-23 11:53:35 发布

26.5.5 进行一波大更新，复习一下并查集基操

裸并查集

基本功能

将两个集合合并
询问两个元素是否在一个集合当中

基本原理
每个集合用一棵树来表示。树根的编号就是整个集合的编号。每个节点存储它的 parent 节点，p[x] 表示 x 的 parent 节点。

find(x) 返回的是 x 所在的集合（根节点）编号

int find(int x){
	if(p[x]!=x) return find(p[x]);
	return x;
}

也等价于

while (p[x] != x) x = p[x];

区别就是递归写法容易爆栈，while 不容易爆栈。

三个问题

问题1：如何判断树根

if (p[x] == x) 则 x 是树根

问题2：如何求 x 的集合编号

px = find(x)

接着询问两个元素是否在一个集合当中

if (find(x) == find(y)) 则在一个集合中

问题3：如何合并两个集合

p[find(x)] = find(y)

但是一般不用裸的并查集，一般都会加一步简单但显著的优化：

基本优化&并查集最核心操作：路径压缩

就是在 find 函数中增加一个路径压缩，在 return 的时候把 x 路径上的所有节点都直接指向根节点。这一步优化使得 find 的时间复杂度近似于 $O (1)$ .

int find(int x){
	if(p[x]!=x) return p[x]=find(p[x]);
	return x;
}

另一个优化是按秩合并，就是在合并的时候倾向于把矮的树合并到高的树上去，实际上并没有多少优化效果，基本没用，可以忽略

维护额外信息：求集合中点的个数

在无向图中，可以把连通块看成集合，在输入时不断加边的过程就是在合并集合，求连通块的个数也就是求集合个数，求每个连通块内点的个数就是求集合中点的个数。

需要增加一个数组 siz[i] 来维护每个集合中点的个数，并且只有 i==根节点 的时候，siz[i] 才有意义。维护的步骤仅需要在合并集合的同时进行

siz[find(b)] += siz[find(a)]
p[find(a)] = find(b)

有的时候题目会给重边，这时候在合并之前要判断一下a、b 是不是本来就在一个集合中。

练习——维护额外信息：集合中边的数量

2026码蹄杯第二场 MC0562 题目简化表述

给定一个包含 $n$ 个点、 $m$ 条边的简单无向图。

对于每一条边，都必须把它分配给它的两个端点之一。对于每个点，统计最终分配给它的边数。如果某个点被分配到的边数是奇数，则称这个点为优秀点。

求最多可以有多少个优秀点。

输入格式

第一行输入两个整数 $n, m$ ，表示点数和边数。

接下来 $m$ 行，每行输入两个整数 $u, v$ ，表示 $u$ 和 $v$ 之间有一条无向边。

输出格式

输出一个整数，表示最多可以得到多少个优秀点。

数据范围

$\le n, m \le 2 \times 10^5$

$\le u, v \le n$

图为简单无向图，即无重边。

样例

输入：

输出：

这个题有一定的思维含量，需要通过观察得出结论，然后才能用并查集求解。

关键观察是：每个连通块可以独立考虑。设某个连通块有 $V$ 个点、 $E$ 条边。无论怎么分配边，这个连通块内所有点被分配到的边数总和一定是 $E$ ，所以“奇数点”的个数必须和 $E$ 同奇偶。

用数学表述：在这个连通块中，优秀点数量 $x$ 必须满足： $\equiv E \pmod 2$ ，（同时显然 $\le V$ ）。

接下来要让 $x$ 尽量大。如果 $V$ 和 $E$ 同奇偶，那么可以让所有 $V$ 个点都是优秀点，答案贡献就是 $V$ 。如果 $V$ 和 $E$ 不同奇偶，那么 $V$ 个优秀点不合法，只能少一个，答案贡献就是 $V - 1$ 。

所以每个连通块的贡献是：如果 $\equiv E \pmod 2$ ，贡献为 $V$ ；否则贡献为 $V - 1$ 。

因此做法很简单：用并查集求出每个连通块的点数 $V$ 和边数 $E$ ，然后按上面的规则累加答案。

#include<bits/stdc++.h> 

using namespace std;
const int N=2e5+10;
int n, m, cnt;
int p[N], v[N], e[N];

int find(int x){
    if(p[x]!=x) return p[x]=find(p[x]);
    else return x;
}

void merge(int x, int y){
    int px=find(x), py=find(y);
    if(px==py){
        e[px]++;
        return;
    }
    p[px]=py;
    v[py]+=v[px];
    e[py]+=e[px]+1;	// 就在加边的时候 合并两个集合的边数再外+1
}

int main( )
{
    scanf("%d%d",&n ,&m);
    for(int i=1; i<=n; i++) p[i]=i, v[i]=1;
    while(m--){
        int u, v;
        scanf("%d%d",&u, &v);
        merge(u,v);
    }
    for(int i=1; i<=n; i++){
        if(p[i]==i){
            if((v[i]^e[i])%2==0) cnt+=v[i];
            else cnt+=v[i]-1;
        }
    }
    printf("%d",cnt);
    return 0;
}

维护复杂关系：带权与扩展域

带权并查集

以经典的【NOI2001】“食物链”问题为例。题目中有 n 个动物，它们属于三类之一，并且三类之间构成循环捕食关系：A 吃 B，B 吃 C，C 吃 A。接下来会给出 k 句话，每句话会给出 op x y ，有两种形式：

op==1 “x 和 y 是同类”。
op==2 “x 吃 y”。

但是这些话不一定都是真的。我们需要按照输入顺序判断每句话是否与前面已经确认的信息矛盾，如果矛盾，就把它计为假话。最后输出假话的总数。

题目难点不在于判断单独一句话，而在于“关系会不断累积”。例如已经知道 x 和 y 同类，又知道 y 吃 z，那么之后再出现 x 吃 z 就应该被判断为真；如果出现 z 吃 x，就应该被判断为假。这说明我们需要维护的不只是两个点是否在同一个集合中，还要维护它们之间的相对关系。

分析

普通并查集只能回答一个问题：两个元素是否属于同一个集合。它适合维护“连通性”或者“等价关系”，比如判断两个人是否在同一个朋友圈中。但是这道题里，元素之间不只是“在不在同一组”，还有更具体的关系：

x 和 y 同类
x 吃 y
x 被 y 吃

因此需要使用带边权的并查集。

带边权并查集的核心思想是：在维护父节点 p[x] 的同时，再额外维护一个权值 d[x]，表示 x 和父节点 p[x] 之间的关系。经过路径压缩后，d[x] 就可以表示 x 和所在集合根节点之间的关系。

在这道题中，因为食物链关系是三类循环，所以可以用 mod 3 来表示关系。

也就是说，如果 d[x] 表示 x 到根节点的关系，那么对于同一个集合中的两个点 x 和 y，可以通过这个公式判断 x 和 y 的关系：

(d[x] - d[y] + 3) % 3 = k

那么我们就可以规定结果 k 及其表示：

k=0：x 和 y 是同类
k=1：x 吃 y
k=2：x 被 y 吃

每次读入一句话时，先判断 x、y 是否越界。如果越界，这句话一定是假话。然后找出 x 和 y 的根节点。

如果 x 和 y 已经在同一个集合中，说明它们之间的关系已经可以由前面的信息推出。此时只需要检查当前这句话是否和已有关系矛盾。

如果 x 和 y 不在同一个集合中，说明这句话提供了新的信息。此时不能简单合并集合，还必须计算出两个集合根节点之间的关系，也就是维护好新的 d[px]，让合并之后整个集合内部的相对关系仍然成立。

这个时候，我们默认选择把x合并到y上，有了如下示意图

        d[px]
    px --------> py
    ^            ^
    |            |    
d[x]|            |d[y]
    |            |
    x            y

在模3的意义下，将式子 d[x]+d[px]-d[y]= k 移项之后，我们需要维护的 d[px] 就是 d[px] = d[y] - d[x] + k，修改为在 mod 3 的意义下就变成了：

d[px]=(d[y]-d[x]+k+3)%3;

find 函数也要维护 d[x] ，以下这两种写法都可以。

第一种：
先 find(p[x])，但暂时不改 p[x]。
所以 p[x] 仍然指向旧父节点，可以直接用 d[p[x]]。

int find(int x){
    if(p[x]!=x){
        int u=find(p[x]);
        d[x]=(d[x]+d[p[x]])%3;        
        p[x]=u;
    }
    return p[x];
}

第二种：
先保存旧父节点 u。
然后可以直接改 p[x]。
最后用 d[u] 找到旧父节点的关系。

int find(int x){
    if(p[x]!=x){
        int u=p[x];
        p[x]=find(p[x]);
        d[x]=(d[x]+d[u])%3;
    }
    return p[x];
}

核心公式永远是：

d[x] = (d[x] + d[旧父节点]) % 3;

第一种写法里，旧父节点还在 p[x] 里，u 存的是根节点；第二种写法里，旧父节点被提前保存到 u 里。个人感觉还是第二种更易于理解一些，并且和朴素并查集板子的关联更紧密一些。

完整代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1e5+10;
int n, k, cnt;
int p[N], d[N];
/*
mod 3 意义下
dx-dy 余 1 表示 x 吃 y
dx-dy 余 2 表示 y 吃 x
dx-dy 余 0 表示 x 与 y 是同类
*/

int find(int x){
    if(p[x]!=x){
        int u=p[x];
        p[x]=find(p[x]);
        d[x]=(d[x]+d[u])%3;
    }
    return p[x];
}

int main(){
    scanf("%d%d", &n, &k);
    for(int i=1; i<=n; i++) p[i]=i;
    for(int i=1; i<=k; i++){
        int op,x,y;
        scanf("%d%d%d",&op,&x,&y);
        if(x>n||y>n){
            cnt++; continue;
        }
        if(x==y && op==2){
            cnt++; continue;
        }
        
        int px=find(x), py=find(y);
        
        if(px==py){          // 已经在一个集合 此时需要判断真假
            if(op==1)        // x y应该是同类
                if((d[x]-d[y]+3) %3 !=0) cnt++;
            else             // x 应该吃 y
                if((d[x]-d[y]+3) %3 !=1) cnt++; 
        }
        else{                // 不在一个集合 需要合并集合、维护d
            p[px]=py;        // 把x的根节点接到y的根节点上
            if(op==1)        // x y 是同类
                d[px]=(d[y]-d[x]+3)%3;
            else             // x吃y 
                d[px]=(d[y]-d[x]+1+3)%3;
        }
    }
    printf("%d", cnt);
    return 0;
}

扩展域并查集

普通并查集只能维护 x 和 y 是否属于同一类，但是很多题不只是“同类关系”，还会有“敌人关系”“捕食关系”“相差关系”等。扩展域并查集，就是把“一个元素”拆成多个“虚拟元素”，然后用普通并查集维护这些状态之间的等价关系。

还是以刚刚的食物链为例。我们可以把每个动物 x 拆成 3 个点：

x          表示 x 所属的种类
x + n      表示 x 吃的种类
x + 2n     表示吃 x 的种类

也可以理解为：

x 的 A 域（同类域）：和 x 同类
x 的 B 域（捕食域）：被 x 吃
x 的 C 域（天敌域）：吃 x

这样原来有 n 个点，现在变成了 3n 个点。

例如，如果一句话说：

x 和 y 是同类

那就要合并三组关系：

merge(x, y);						// x 的同类 = y 的同类
merge(x + n, y + n);				// x 吃的 = y 吃的
merge(x + 2 * n, y + 2 * n);		// 吃 x 的 = 吃 y 的

如果一句话说：

x 吃 y

那么应该是：

merge(x, y + 2 * n);				// x 的同类 = 吃 y 的种类
merge(x + n, y);					// x 吃的种类 = y 的同类
merge(x + 2 * n, y + n);			// 吃 x 的种类 = y 吃的种类

当然，不同人的域定义可能不同，所以合并写法也可能换一种。但是核心思想不变：把复杂关系转换成若干个“相等关系”。

扩展域并查集常见于两类问题。
第一类是二分图、敌人关系。每个点拆成两个：
x：x 属于正方阵营
x + n：x 属于反方阵营
如果 x 和 y 是敌人，就合并：merge(x, y + n); merge(x + n, y);
如果发现：find(x) == find(x + n) 说明 x 既在正方，又在反方，矛盾。

第二类是“食物链”这种模 3 关系。每个点拆成三个：
x
x + n
x + 2n
分别表示同类、捕食对象、天敌。

完整代码

#include <bits/stdc++.h>
using namespace std;
int p[200000];
int n,m,op,x,y,ans;
int find(int x){
    if(x==p[x]) return x;
    return p[x]=find(p[x]);
}
void merge(int x,int y){
    p[find(x)]=find(y);
}
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1; i<=3*n; i++) p[i]=i;		// 初始化的时候要3n的空间
    for(int i=1; i<=m; i++){
        scanf("%d%d%d",&op,&x,&y);
        if(x>n || y>n) ans++;
        else if(op==1){		// x y是同类
            if(find(x)==find(y+n) || find(x)==find(y+n+n)) ans++;
            else{
                merge(x,y);
                merge(x+n,y+n);
                merge(x+n+n,y+n+n);
            }
        }
        else{				// x 吃 y
            if(x==y || find(x)==find(y) || find(x)==find(y+n)) ans++;
            else{
                merge(x,y+n+n);		//y的捕食域加入x
                merge(x+n,y);		//x的天敌域加入y
                merge(x+n+n,y+n);	//x的捕食域是y的同类域.
            }
        }
    }
    printf("%d\n", ans);
}

带权与扩展域的区别和联系

扩展域并查集可以看作带权并查集在“关系种类有限”时的一种展开写法；它用空间换直观性。带权并查集则直接维护点到根节点的关系值，空间更省，也能处理更一般的权值关系。

实际上，涉及多种关系的题目基本都可以用这两种方法做。对于有限关系类型的问题，带权并查集和扩展域并查集通常可以互相转化；对于无限或大范围权值关系的问题，带权并查集更通用，扩展域并查集不适合。

题

并查集板子

现在有一个并查集，你需要完成合并和查询操作。
输入格式
第一行包含两个整数 $N, M$ ,表示共有 $N$ 个元素和 $M$ 个操作。
接下来 $M$ 行，每行包含三个整数 $Z_i,X_i,Y_i$ 。
当 $Z_i=1$ 时，将 $X_i$ 与 $Y_i$ 所在的集合合并。
当 $Z_i=2$ 时，输出 $X_i$ 与 $Y_i$ 是否在同一集合内，是的输出
Y ；否则输出 N 。
输出格式
对于每一个 $Z_i=2$ 的操作，都有一行输出，每行包含一个大写字母，为 Y 或者 N 。
输入 #1

输出 #1

N
Y
N
Y

const int N=10010;
int n,m;
int p[N];

int find(int k){
	if(p[k]==k) return p[k]=find(p[k]);
	return k;
}

int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++) p[i]=i;
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>z>>x>>y;
		if(z==1) 				//合并
			p[find(x)]=find(y);
		else {					//查询
			if(find(x)==find(y)) 
				cout<<"Y"<<endl;
			else 
				cout<<"N"<<endl;
		}
	}
}

P5937 [CEOI1999]Parity Game

（afo之前写的一道题难在思维现在都不知道之前是怎么写出来的了）

做法一：扩展域并查集+离散化

#include<iostream>
#include<cstdio>
#include<unordered_map> //c++11新特性 需要在编译环境里加入指令 -std=c++11
using namespace std;
const int N=1e5+10;
int n,m,idx;
int p[N*2+10];
unordered_map<int,int>s;
int read(){
	int x=0,f=1; char ch=getchar();
	if(ch=='-') f=-1, ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
	return x*f;
}

int get(int x){
	if(s.count(x)==0) s[x]=++idx;
	return s[x];
}
int find(int x){
	if(x==p[x]) return x;
	else return p[x]=find(p[x]);
}
int main(){
	n=read(); m=read(); int res=m;
	for(int i=1;i<=N*2;i++) p[i]=i;//注意初始化
	for(int i=1;i<=m;i++){
		int x=read(), y=read(), t;
		string op; cin>>op;
		if(op=="even") t=0;
		else t=1;
		x=get(x-1); y=get(y);
		if(t==0){
			if(find(x+N)==find(y)) {
				res=i-1; break;
			}
			else{
				p[find(x)]=find(y);
				p[find(x+N)]=find(y+N);
			}
		}	
		else{
			if(find(x)==find(y)){
				res=i-1; break;
			}
			else {
				p[find(x+N)]=find(y);
				p[find(x)]=find(y+N);
			}
		}	
	}
	printf("%d",res);
}

做法二：带权并查集

#include<iostream>
#include<cstdio>
#include<map>
using namespace std;
const int N=2e5+10;
int n,m,res;//长度 询问数
int idx;//编号 
int p[N]; //父亲数组 
int d[N]; //边权 
map<int,int>s;
int read(){
	int x=0,f=1; char ch=getchar();
	if(ch=='-') f=-1, ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<1)+(x<<3)+(ch^48), ch=getchar();
	return x*f;
}
int get(int x){
	if(s.count(x)==0) s[x]=++idx;
	return s[x];
}
int find(int x){
	if(p[x]!=x){
		int root=find(p[x]);
		d[x]^=d[p[x]]; //压缩路径
		p[x]=root;
	}
	return p[x];
}

int main(){
	n=read();
	m=read();
	res=m;
	for(int i=1;i<=N;i++) p[i]=i; //初始化！！！！！
	//注意离散化之后 数据量<=m 初始化到N 
	for(int i=1;i<=m;i++){
		int x=read(), y=read();
		string op; cin>>op;
		int a=get(x-1), b=get(y);
		int pa=find(a), pb=find(b);
		if(op=="even"){
			int t=0;
			if(pa==pb){
				if((d[a]^d[b])!=t){
					res=i-1; break;
				}
			}
			else {
				p[pa]=pb;
				d[pa]=d[a]^d[b]^t;
			}
		}
		else{
			int t=1;
			if(pa==pb){
				if((d[a]^d[b])!=t){
					res=i-1; break;
				}
			}
			else{
				p[pa]=pb;
				d[pa]=d[a]^d[b]^t;
			}
		}
	}
	printf("%d",res);
}

AtomGit开源社区

AtomGit 是由开放原子开源基金会联合 CSDN 等生态伙伴共同推出的新一代开源与人工智能协作平台。平台坚持“开放、中立、公益”的理念，把代码托管、模型共享、数据集托管、智能体开发体验和算力服务整合在一起，为开发者提供从开发、训练到部署的一站式体验。

更多推荐

如何下载Claude并接入GLM

本文详细介绍了Claude的安装配置及接入GLM5.0模型的全过程。首先需检查Node.js和Git环境，建议使用淘宝镜像加速npm安装。通过npm安装Claude后，需在智谱AI平台获取API Key。重点讲解了claude-code-router的配置方法，包括创建config.json和settings.json配置文件，并设置GLM-5.1模型参数。最后指导用户测试运行，若出现400错误需

AtomGit开源社区

BP神经网络对水质问题进行预测（Matlab代码实现）

本文探讨了BP神经网络在水质预测中的应用，通过构建BP神经网络模型，利用历史水质监测数据对未来水质参数进行预测。研究表明，BP神经网络在水质预测中表现出较高的准确性和可靠性，能够为水资源保护和管理提供科学依据。

AtomGit开源社区

考虑分布式电源不确定性的配电网鲁棒动态重构模型与求解方法（Matlab代码实现）

在双碳战略与新型电力系统建设背景下，以光伏、风电为代表的分布式电源在配电网中得到大规模接入，使得传统配电网由单向无源辐射网络，逐步转变为多电源供电、潮流双向流动的有源配电网。分布式电源出力具有明显的间歇性、随机性与波动性，传统确定性配电网重构方法难以适应强不确定性运行场景，容易出现重构方案失效、线路潮流越限、系统网损上升、供电可靠性降低等问题。为提升配电网在源荷双重不确定条件下的安全稳定与经济运行