我们提供安全，免费的手游软件下载！

安卓手机游戏下载_安卓手机软件下载_安卓手机应用免费下载-先锋下载

当前位置: 主页 > 软件教程 > 软件教程

Google相机 正版 Google相机 正版 漫酷阅读器 官网下载安装手机版 漫酷阅读器 官网下载安装手机版 漫酷阅读器 免费下载 漫酷阅读器 免费下载 多看阅读 app官方版 多看阅读 app官方版 拷贝漫画 app官网入口2024版 拷贝漫画 app官网入口2024版 kuyo加速器 官方免费下载版 kuyo加速器 官方免费下载版 DNF助手 2025最新版 DNF助手 2025最新版 次元盒子 次元盒子 迅猛兔加速器 免费下载入口 迅猛兔加速器 免费下载入口 迅猛兔加速器 2025最新版 迅猛兔加速器 2025最新版

并查集扩展

来源：网络 更新时间：2024-08-18 09:31:37

并查集扩展

普通并查集

例题:

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 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> 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 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& a,int i){
	int t = lower_bound(a.begin(),a.end(),i) - a.begin() + 1;
	return t;
}
void solve(){
	int n;
	cin >> n;
	vector v1;
	vector> ys;
	vector> ns;
	vector 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<

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 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> 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 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 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 <

方法二: 

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 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 <

相关资讯

Go中数组和切片

11-14

使用鸿蒙NEXT框架开发光强仪应用

11-14

DDCA —— 内存架构和子系统&内存控制器

11-14

如何使用Spring Boot进行文件压缩处理

11-14

淘宝双12津贴领取教程

11-13

Spring AI 再更新：如何借助全局参数实现智能数据库操作与个性化待办管理

11-13

如何在OpenAI Gym中创建自定义环境

11-12

功能权限和数据权限在系统中的作用

11-11

在 Github Action 管道内集成 Code Coverage Report

11-11

Nuxt.js 应用中的 listen 事件钩子详解

11-10

热门攻略

热门资讯

如何使用Spring Boot进行文件压缩处理11-14

Spring AI 再更新：如何借助全局参数实现智能数据库操作与个性化待办管理11-13

功能权限和数据权限在系统中的作用11-11

在 Github Action 管道内集成 Code Coverage Report11-11

好未来：多云环境下基于 JuiceFS 建设低运维模型仓库11-09

热门游戏

安卓软件
系统工具 拍照摄影 主题美化 生活服务 趣味娱乐 资讯阅读 育儿母婴 手游辅助
安卓游戏
射击枪战 策略塔防 休闲益智 动作闯关 冒险解谜 赛车竞速 手机网游 体育运动
资讯
新闻资讯 科技周边
网站地图
Copyright © 2007- 2023 www.91xfw.com. All Rights Reserved.苏ICP备20025626号