算法------（11）并查集

例题：

（1）Acwing 836.合并集合

        并查集就是把每一个集合看成一棵树，记录每个节点的父节点。合并集合就是把一棵树变成另一棵树的子树，即把一棵树的父节点变为另一棵树的父节点的儿子。查询是否在同一集合就是看他们的根节点是否相同。在查找过程中可以路径加速，把每个点直接连到根节点。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int p[N];
int find(int x){
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i = 1;i<=n;i++){
        p[i] = i;
    }
    for(int i = 0;i<m;i++){
        char op[2];
        int x,y;
        scanf("%s%d%d",op,&x,&y);
        if(op[0] == 'M'){
            p[find(x)] = find(y);
        }
        else{
            if(find(x)==find(y)) printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

(2) Acwing 837.连通块中点的数量

         并查集板子题，把每个联通块当成一棵树，连边操作就等于将联通块合并，查询是否在同一个联通块中就等于查询其根节点是否相同，询问数量需要额外维护一个size数组，每次合并时根节点的size要加上被合并的根节点的size。如果合并时两个节点的根节点相同则无需合并，否则size会加倍。

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int sz[N],p[N];
int find(int x){
    if(p[x]!=x) p[x] = find(p[x]);
    return p[x];
}
int main()
{
    int n,m;
    scanf("%d%d", &n, &m);
    for(int i = 1;i<=n;i++){
       p[i] = i;
       sz[i] = 1;
    }
    for(int i = 0;i<m;i++){
        char op[2];
        int x,y;
        scanf("%s",op);
        if(op[0] == 'C'){
            scanf("%d%d", &x, &y);
            if(find(x)!=find(y)){
                sz[find(x)] += sz[find(y)];
                p[find(y)] = find(x);
            }
        }
        else if(op[1] == '1'){
            scanf("%d%d", &x, &y);
            if(find(x) == find(y)) printf("Yes\n");
            else printf("No\n");
        }
        else{
            scanf("%d", &x);
            printf("%d\n",sz[find(x)]);
        }
    }
    return 0;
}

（3）AcWing 240. 食物链

        由于是一个环形食物链，因此可以使用带权并查集，记录每个节点到根节点的距离，通过%3所得的数判断两者间的关系。具体代码有注释。 

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int d[N],p[N];
int find(int x){
    if(p[x]!=x){
        int t = find(p[x]);//把该点的父节点以上的所有节点全部连到根节点
        d[x] += d[p[x]];//此时d[p[x]]就是p[x]到根节点的距离
        p[x] = t;//p[x]连到根节点
    }
    return p[x];
}
int main()
{
    int n,m,res = 0;
    scanf("%d%d", &n, &m);
    for(int i = 1;i<=n;i++){
        p[i] = i;
    }
    while (m -- ){
        int s,x,y;
        scanf("%d%d%d",&s, &x, &y);
        if(x>n||y>n){
            res++;
            continue;
        }
        else if(s == 1){
            int px = find(x),py = find(y);
            if(px == py){
                if((d[x]-d[y])%3) res++;//同类则模0
                continue;
            }
            else{
                p[px] = py;
                d[px] = d[y] - d[x];
            }
        }
        else{
            int px = find(x),py = find(y);
            if(px == py){
                if((d[x]-d[y]-1)%3) res++;//可能存在一正一负因此不能==1
                continue;
            }
            else{
                p[px] = py;
                d[px] = d[y] - d[x] + 1;
            }
        }
    }
    printf("%d",res);
    return 0;
}

练习：（1）Leetcode 128.最长相关序列

         把数组里的每一个数看做一个节点，而每个节点可以与权值比自己本身权值小1的节点相连。对于数组中的每个数，如果权值比他小1的数在哈希表中存在并且两者不具有相同的根结点时，由于数组中不存在重复元素，且每次只会把大的数接在小的数后面，因此两者集合必然是连续的。所以先进行去重然后开始建树，由于存在负数因此利用哈希表储存每个数的下标防止访问越界。问题可以转化为最大的联通块中点的数量。

class Solution {
public:
    unordered_map<int,int> x;
    int p[100010],sz[100010];
    int find(int x){
        if(p[x]!=x) p[x] = find(p[x]);
        return p[x];
    }
    int longestConsecutive(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        nums.erase(unique(nums.begin(),nums.end()),nums.end());
        int n = nums.size();
        for(int i = 1;i<=n;i++){
            x[nums[i-1]] = i;
            p[i] = i;
            sz[i] = 1;
        }
        for(int i = 0;i<n;i++){
            if(x[nums[i]-1]&&find(x[nums[i]-1]) != find(x[nums[i]]) ){
                sz[find(x[nums[i]-1])] += sz[find(x[nums[i]])];
                p[find(x[nums[i]])] = find(x[nums[i]-1]);
            }
        }
        int ans = 0;
        for(int i = 0;i<n;i++){
            if(p[x[nums[i]]] == x[nums[i]]) ans = max(ans,sz[x[nums[i]]]);
        }
        return ans;
    }
};

（2）Leetcode 684.冗余连接

        没做出来。。

        遍历每条边，如果该边的两个端点属于一个集合内，那么就说明这条边导致了一个环的构成。返回这条边。否则把两个端点加到同一个集合内。由于题目规定只会多出一条边（只会存在一个环），因此出现的这条边一定是构成环的最后一条边，因为假如后面还存在能构成环的边则不满足只有一个环的条件，因此这条边就是构成环的最后一条边。

class Solution {
public:
    int p[1010];
    int find(int x){
        if(p[x]!=x) p[x] = find(p[x]);
        return p[x];
    }
    vector<int> findRedundantConnection(vector<vector<int>>& edges) {
        int n = edges.size();
        for(int i = 1;i<=n;i++) p[i] = i;
        for(auto c:edges){
            int a = find(c[0]),b = find(c[1]);
            if(a==b) return{c[0],c[1]};
            else{
                p[a] = b;
            }
        }
        return {0,0};
    }
};

(3)Leetcode 1202.交换字符串中的元素

        并查集应该不是最佳解。。不过没想出来啥别的方法。。

        第一步：把所有能交换的位置构成一个集合。第二步：遍历字符串，把每个字母加入其根节点映射的优先队列（可以自动按字典序排序）第三步：遍历字符串，用一个空字符串记录结果。在每个字母对应的位置放上其根节点对应的优先队列中第一个字母（按字典序最小的字母），然后该元素出队。

class Solution {
public:
    int p[100010];
    int find(int x){
        if(p[x]!=x) p[x] = find(p[x]);
        return p[x];
    }
    string smallestStringWithSwaps(string s, vector<vector<int>>& pairs) {
        unordered_map<int,priority_queue<int,vector<int>,greater<int>>> x;
        int n = s.length();
        for(int i = 0;i<n;i++) p[i] = i;
        for(auto c:pairs){
            int a = find(c[0]),b = find(c[1]);
            if(a!=b) p[a] = b;
        }   
        for(int i = 0;i<n;i++) x[find(i)].push((int)s[i]);
        string res = "";
        for(int i = 0;i<n;i++){
            char ch = (char)x[find(i)].top();
            x[find(i)].pop();
            res+=ch;
        }
        return res;
    }
};

(4)Leetcode 886.可能的二分法

        判断二分图的最好方法并不是并查集，但是。。用并查集没做出来。。

        把每一个人的关系不好的人放入一个集合中，如果这个集合的人里面有人跟该人的根节点相同说明其属于同一个集合，不成立，反之则把他们加入同一个集合。

class Solution {
public:
    unordered_map<int,vector<int>> x;
    int p[2010];
    int find(int x){
        if(p[x]!=x) p[x] = find(p[x]);
        return p[x];
    }
    bool possibleBipartition(int n, vector<vector<int>>& dislikes) {
        if(!dislikes.size()) return true;
        for(auto c:dislikes){
            x[c[0]].push_back(c[1]);
            x[c[1]].push_back(c[0]);
        }
        for(int i = 1;i<=n;i++) p[i] = i;
        for(int i = 1;i<=n;i++){
            if(x[i].empty()) continue;
            int a = find(i),b = find(x[i][0]);
            for(auto c:x[i]){
                if(find(c) == a) return false;
                p[find(c)] = b;
            }
        }
        return true;
    }
};

（5) P8686 [蓝桥杯 2019 省 A] 修改数组

         。。。其实还是没太理解。。

        首先把每一个数的根节点设为其本身，然后对于每次输入的数，如果其根节点为本身，说明其第一次出现，因此把根节点更新为原先的根节点+1，否则查找其根节点（由于每次都加1，因此 从 其本身 到 其根节点-1 都已经出现过），然后输出根节点并且把 根节点+1 作为根节点的新父节点（这个父节点有可能还会有父节点，但并不影响，可以理解为两条链相连成为一条更长的新链）

        初始化时要把后面的节点一起初始化，否则更新时由于后续某些节点的根节点变为0就会出错。。

#include <iostream>
using namespace std;
const int N = 100010;
typedef long long ll;
ll p[N];
ll find(ll x){
	if(p[x]!=x) p[x] = find(p[x]);
	return p[x];
} 
int main(int argc, char** argv) {
	ll n;
	scanf("%d",&n);
	for(int i = 1;i<=100010;i++) p[i] = i;
	for(int i = 1;i<=n;i++){
		ll x;
		scanf("%lld",&x);
		printf("%lld ",find(x));
		p[find(x)] = find(x) + 1;
	}
	return 0;
}

（7）洛谷 P1111 修复公路

        。。很烦。。        

        联通块的个数为1时就能完全通车。首先按照时间排序（分清路的条数和村庄的个数！！），然后遍历每一条路，假如两个路边上的村庄共用一个根节点则无视，否则联通块数-1，把两个村庄联通。每次判断所有联通块是否只剩一个，如果是则输出当前时间戳，如果最后还剩不止一个联通块则输出-1。这里判断联通块个数不需要每一次都遍历，只需要维护联通块个数即可（因为一开始每一个村庄就是一个联通块）

#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1010,M = 100010;
struct Node{
	int x,y,t; 
	bool operator< (Node &a){
		return t < a.t;
	}
}road[M];
int p[N];
int find(int x){
	if(p[x]!=x) p[x] = find(p[x]);
	return p[x];
}
int main(int argc, char** argv) {
	int n,m;
	scanf("%d%d",&n,&m);
	int res = n; 
	for(int i = 1;i<=n;i++) p[i] = i;
	for(int i = 0;i<m;i++){
		scanf("%d%d%d",&road[i].x,&road[i].y,&road[i].t);
	}
	sort(road,road+m);
	bool flag = 0;
	for(int i = 0;i<m;i++){
		int a = find(road[i].x),b = find(road[i].y),c = road[i].t;
		if(a == b) continue;
		else{
			res--;
			if(res==1){
				printf("%d",c);
				flag = 1;
				break;
			}
			p[a] = b;
		}
	}
	if(!flag) printf("-1");
	return 0;
}

(8)洛谷 P1455 搭配购买

        一个缝合题，01背包加并查集。。01背包写的很差，还是不太会用滚动数组。。后面再补一下吧。。

        用并查集把多个商品合成为一个商品，根节点代表商品本身。01背包不用滚动数组会MLE。更新时注意是更新根节点的价格和价值（因为是连接根节点）。

#include <iostream>
using namespace std;
const int N = 1e4+10;
int w[N],v[N],p[N],f[N];
struct Node{
	int w,v;
}shop[N];
int find(int x){
	if(p[x]!=x) p[x] = find(p[x]);
	return p[x];
}
int main(int argc, char** argv) {
	int n,m,w1;
	scanf("%d%d%d",&n,&m,&w1);
	for(int i = 1;i<=n;i++){
		scanf("%d%d",&w[i],&v[i]);
		p[i] = i;
	}
	for(int i = 0;i<m;i++){
		int a,b;
		scanf("%d%d",&a,&b);
		a = find(a),b = find(b);
		if(a==b) continue;
		p[a] = b;
		w[b] += w[a];
		v[b] += v[a];
	}
	int cnt = 1;
	for(int i = 1;i<=n;i++){
		if(p[i]!=i) continue;
		shop[cnt].w = w[i];
		shop[cnt].v = v[i];
		cnt++;
 	}
	for(int i = 1;i<=n;i++){
		for(int j = w1;j>=shop[i].w;j--){
			f[j] = max(f[j],f[j-shop[i].w] + shop[i].v);
		}
	}
	printf("%d",f[w1]);
	return 0;
}

（9）P3420 SKA-Piggy Banks

        虽然做出来了。。但是感觉还是搞不太明白。。

        这道题之所以可以用并查集的原因并不是因为罐子之间存在钥匙联系，而是一个罐子只有一个钥匙且在另一个罐子里，但一个罐子可以装多把钥匙。因此我们每次把钥匙对应的罐子连在存放钥匙的罐子后面，则打开根节点的罐子就可以打开所有罐子。因此一个集合内的罐子就一定只需要打开一个罐子，题目也就改为求联通块的数目。因此这道题用并查集可以做的原因其实是每个钥匙唯一且对应了一个罐子。假如题目改为第i个数代表第i个罐子存放了第ai个罐子的钥匙，这道题就不能用并查集做了。。https://www.luogu.com.cn/discuss/684322icon-default.png?t=N7T8https://www.luogu.com.cn/discuss/684322        这是比较专业的解答。。。我只能用自己的角度去解释。。解释的不太好。。

（10）P1196 [NOI2002] 银河英雄传说

        。。确实是挺难的。。

        为了查询两个战舰之间的战舰数目，我们维护每一个战舰到根节点的距离，这样两个战舰之间的战舰数目就是到根节点的距离差-1。而由于我们维护到根节点的距离还需要知道当前集合内的战舰数量，因此还需要维护一个数组用来记录每个集合（根节点下）的战舰数。当然，由于每个节点都没法在合并时就被更新，因此我们可以在find函数时对每个节点进行更新。 

#include <iostream>
using namespace std;
const int N = 30010;
int p[N],dis[N],num[N];
int find(int x){
	if(p[x]!=x){
		int k = p[x]; 
		p[x] = find(p[x]);
		dis[x] += dis[k];
		num[x] = num[p[x]];
	}
	return p[x];
}
int main(int argc, char** argv) {
	int t;
	scanf("%d",&t);
	for(int i = 1;i<=30000;i++){
		p[i] = i;
		num[i] = 1;
	}
	while(t--){
		char op[2];
		scanf("%s",op);
		int x,y;
		scanf("%d%d",&x,&y);
		if(op[0] == 'M'){
			x = find(x);
			y = find(y);
			if(x!=y){
				p[x] = y;
				dis[x] = num[y];
				num[y] += num[x];
				num[x] = num[y];
			}
		}
		else{
			if(find(x) == find(y)) printf("%d\n",abs(dis[x] - dis[y])-1);
			else printf("-1\n");
		}
	}
	return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.mfbz.cn/a/381470.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

Linux---网络基础

Linux---网络基础

计算机中的常见概念 协议&#xff08;Protocol&#xff09;&#xff1a; 协议是计算机网络中用于通信的规则和约定的集合。它规定了数据传输的格式、序列、错误检测和纠正方法等。常见的网络协议包括TCP/IP、HTTP、FTP等。 IP地址&#xff08;IP Address&#xff09;&#xf…
阅读更多...
Flink从入门到实践（二）：Flink DataStream API

Flink从入门到实践（二）：Flink DataStream API

文章目录 系列文章索引三、DataStream API1、官网2、获取执行环境&#xff08;Environment&#xff09;3、数据接入&#xff08;Source&#xff09;&#xff08;1&#xff09;总览&#xff08;2&#xff09;代码实例&#xff08;1.18版本已过时的&#xff09;&#xff08;3&…
阅读更多...
kubernetes镜像仓库harbor

kubernetes镜像仓库harbor

一、镜像仓库的种类 GitHub GitHub有付费版和免费版，目前默认的docker镜像拉取策略是从GitHub上进行拉取gitee 国内harbor私有仓库二、harbor仓库规划设计 私有镜像仓库 Harbor 安装和配置 新创建一台虚拟机安装harbor， 配置如下: 主机名ip配置网络harbor192.168.1.204VCPU/…
阅读更多...
基于springboot会员制医疗预约服务管理信息系统源码和论文

基于springboot会员制医疗预约服务管理信息系统源码和论文

会员制医疗预约服务管理信息系统是针对会员制医疗预约服务管理方面必不可少的一个部分。在会员制医疗预约服务管理的整个过程中&#xff0c;会员制医疗预约服务管理系统担负着最重要的角色。为满足如今日益复杂的管理需求&#xff0c;各类的管理系统也在不断改进。本课题所设计…
阅读更多...
MacOS - 菜单栏上显示『音量』

MacOS - 菜单栏上显示『音量』

教程步骤 点击打开系统偏好『设置』&#xff0c;并找到『控制中心』 在『控制中心模块』找到『声音』&#xff0c;选择『始终在菜单栏显示』
阅读更多...
js库和js框架你还分不清吗？一句话就讲明白了。

js库和js框架你还分不清吗？一句话就讲明白了。

一、JS库 JS库&#xff08;JavaScript Library&#xff09;是一组封装了常用功能和工具的JavaScript代码集合。它们提供了一系列的函数和方法&#xff0c;使得开发者能够更便捷地进行常见的操作和处理。JS库通常是轻量级的&#xff0c;只关注某个特定的功能或问题领域。 一些常…
阅读更多...
JSP编程

JSP编程

JSP编程 您需要理解在JSP API的类和接口中定义的用于创建JSP应用程序的各种方法的用法。此外，还要了解各种JSP组件，如在前一部分中学习的JSP动作、JSP指令及JSP脚本。JSP API中定义的类提供了可借助隐式对象通过JSP页面访问的方法。 1. JSP API的类 JSP API是一个可用于创建…
阅读更多...
MinIO对象存储介绍和使用

MinIO对象存储介绍和使用

一、MinIO介绍 MinIO 是一个开源的对象存储服务器。MinIO 提供了一个强大而灵活的对象存储解决方案&#xff0c;适用于各种规模的应用场景。详细介绍可看官网文档&#xff1a;MinIO对象存储 Windows — MinIO中文文档 | MinIO Windows中文文档 1.1 特点 高性能: MinIO 具有出…
阅读更多...
【nginx】starrocks通过nginx实现负载均衡、故障转移与flink运行SR实战

【nginx】starrocks通过nginx实现负载均衡、故障转移与flink运行SR实战

文章目录 一. 通过nginx实现starrocks负载均衡与故障转移1. 架构逻辑与nginx配置2. nginx相关知识&#xff1a;stream模块和http模块2.1. stream模块2.2. http模块 二. 使用flink 消费SR实战1. Expect: 100-continue 问题1.1. Expect: 100-continue的逻辑1.2. 问题分析与解决 2…
阅读更多...
【Linux系统学习】2.Linux基础命令

【Linux系统学习】2.Linux基础命令

Linux基础命令 Linux的目录结构 Linux命令入门 目录切换相关命令(cd/pwd) 相对路径、绝对路径和特殊路径符 创建目录命令(mkdir) 文件操作命令part1(touch、cat、more&#xff09; 文件操作命令part2(cp、mv、rm&#xff09; 查找命令(which、find&#xff09; grep、wc和管道符…
阅读更多...
【踏雪无痕的痕一】——认知的心病

【踏雪无痕的痕一】——认知的心病

目录 一、背景介绍二、思路&方案三、过程1.教育是最大的"炸片"2.逻辑对等性的认知(时间的保证)3.不要去猜一个人怎么想&#xff0c;要看一个人怎么做4.改变一个人的基础5.你想过和你能过上什么生活完全取决于你自己 四、总结 一、背景介绍 大多数人都只愿意看到…
阅读更多...
结构体数组所有元素（1亿个元素）初始化为相同的值

结构体数组所有元素（1亿个元素）初始化为相同的值

一个结构体数组&#xff0c;有1亿个元素&#xff0c;每个元素都要初始化为相同的值&#xff0c;如果没有现成的语法直接支持这样的初始化操作&#xff0c;就得用for循环写&#xff0c;会不会非常耗时&#xff1f; 如果结构体里的成员都是一些简单的基本数据类型&#xff0c;整…
阅读更多...
AJAX——认识URL

AJAX——认识URL

1 什么是URL&#xff1f; 统一资源定位符&#xff08;英语&#xff1a;Uniform Resource Locator&#xff0c;缩写&#xff1a;URL&#xff0c;或称统一资源定位器、定位地址、URL地址&#xff09;俗称网页地址&#xff0c;简称网址&#xff0c;是因特网上标准的资源的地址&…
阅读更多...
【书生·浦语大模型实战营】学习笔记1

【书生·浦语大模型实战营】学习笔记1

大模型成为发展通用人工智能的重要途经 专用模型&#xff1a;针对特定任务&#xff0c;一个模型解决一个问题 通用大模型&#xff1a;一个模型应对多种任务、多种模态 书生浦语大模型系列 上海人工智能实验室 轻量级、中量级、重量级 7B 和 123B的轻量级和中量级大模型都是开源…
阅读更多...
【C++】map与set的常见使用

【C++】map与set的常见使用

目录 1.关联式容器与序列式容器 2.键值对与pair 3.set 4.map 4.1map的插入与修改 4.2map的迭代器使用 4.3map中[ ]的巧妙用法 1.关联式容器与序列式容器 序列式容器(vector、list、deque…)&#xff1a;其底层为线性序列的数据结构&#xff0c;里面存储的是元素本身。 …
阅读更多...
【Make编译控制 01】程序编译与执行

【Make编译控制 01】程序编译与执行

目录 一、编译原理概述 二、编译过程分析 三、编译动静态库 四、执行过程分析 一、编译原理概述 make&#xff1a; 一个GCC工具程序&#xff0c;它会读 makefile 脚本来确定程序中的哪个部分需要编译和连接&#xff0c;然后发布必要的命令。它读出的脚本&#xff08;叫做 …
阅读更多...
JAVA设计模式之建造者模式详解

JAVA设计模式之建造者模式详解

建造者模式 1 建造者模式介绍 建造者模式 (builder pattern), 也被称为生成器模式 , 是一种创建型设计模式. 定义: 将一个复杂对象的构建与表示分离&#xff0c;使得同样的构建过程可以创建不同的表示。 **建造者模式要解决的问题 ** 建造者模式可以将部件和其组装过程分开…
阅读更多...
内网渗透靶场02----Weblogic反序列化+域渗透

内网渗透靶场02----Weblogic反序列化+域渗透

网络拓扑&#xff1a; 攻击机&#xff1a; Kali: 192.168.111.129 Win10: 192.168.111.128 靶场基本配置&#xff1a;web服务器双网卡机器&#xff1a; 192.168.111.80&#xff08;模拟外网&#xff09;10.10.10.80&#xff08;模拟内网&#xff09;域成员机器 WIN7PC192.168.…
阅读更多...
【开源】基于JAVA+Vue+SpringBoot的人事管理系统

【开源】基于JAVA+Vue+SpringBoot的人事管理系统

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块2.1 管理员功能模块2.2 普通员工功能模块2.3 答辩文案 三、系统展示四、核心代码4.1 查询职称4.2 新增留言回复4.3 工资申请4.4 工资审核4.5 员工请假 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的人…
阅读更多...
AWS云用户创建

AWS云用户创建

问题 需要给工友创建AWS云的用户&#xff0c;这里假设使用分配给自己AWS开发者IAM账号&#xff0c;给别人创建aws IAM账号。 登录系统 打开页面&#xff1a;https://xxx.signin.aws.amazon.com/console&#xff0c;使用分配的开发者账号登录。如下图&#xff1a; 创建用户…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站