响应式网站 外贸,用什么软件做动漫视频网站好,店铺设计软件,南京有哪些做网站的公司一、前言
因为要开始准备年底的校赛和明年年初的ACM、蓝桥杯、天梯赛#xff0c;于是开始按专题梳理一下对应的知识点#xff0c;先从简单入门又值得记录的内容开始#xff0c;并查集首当其冲。
二、我的模板
虽然说是借用了jiangly鸽鸽的板子#xff0c;但是自己也小做…一、前言
因为要开始准备年底的校赛和明年年初的ACM、蓝桥杯、天梯赛于是开始按专题梳理一下对应的知识点先从简单入门又值得记录的内容开始并查集首当其冲。
二、我的模板
虽然说是借用了jiangly鸽鸽的板子但是自己也小做修改了部分命名啥的大体内容并没有修改jiangly鸽鸽yyds
#include bits/stdc.hstruct DisjointSet {int _n;std::vectorint _fa,_size;DisjointSet(){}DisjointSet(int n){init(n);}void init(int n) {_fa.resize(n);std::iota(_fa.begin(),_fa.end(),0);_size.assign(n,1);}int find(int x) {if(x!_fa[x]) {_fa[x] find(_fa[x]);}return _fa[x];}bool same(int x,int y) {return find(x)find(y);}bool merge(int x,int y) {int fx find(x);int fy find(y);if(fx!fy) {_size[fx]_size[fy];_fa[fy] fx;return true;}return false;}
};
三、并查集介绍
并查集disjoint set英文直译过来是不相交的集合。我们中文取名成并查集是因为这类集合主要具有两个操作并和查并即合并两个集合查即查询集合的某些信息。
3.1 并
如果有学习过树的知识那么理解并查集就比较轻松了。“并”操作类似于将森林两棵树转化为一棵树我们只需要让其中一个并查集的根节点的父亲结点指向另外一个并查集的根节点即可。当然选择的时候我们倾向于让深度小的树的根节点指向深度大的树的根节点。不过后续用上路径压缩后谁指向谁基本没有什么太大的影响。实际写代码中我们主要的操作就是对一个并查集的根节点进行修改
3.2 查
1.查询某个节点的根节点 2.查询两个节点是否处于同一个并查集中 3.查询一共有几个并查集 4.查询节点数量最多的并查集和它的节点数量 5.查询节点位于自身并查集的深度
3.3 初始化
在没有进行任何合并前一个并查集的根节点应该为它自身切记写代码的时候不要忘记并查集的初始化当然如果用我的模板的话就不会忘记初始化构造函数已经写好初始化了
3.4 路径压缩
正常来说并查集合并的时间复杂度为O(1)而查询的最坏时间复杂度为O(n)常见的最坏情况就是只有左子树或者只有右子树的一棵树的查询。而如果我们在查询时顺带将查询路径上的结点的父节点属性顺带修改为真正的根节点那么综合下来时间复杂度将会被均摊成O(logn)这是一个非常优秀的优化。
四、专题训练
以我学校OJ题目展开训练
4.1 题目总览 4.2 1520: 数据结构-并查集-家庭问题 思路
这道题是很典型的用并查集做的题目先对并查集进行初始化我们直接把有关系的两人进行合并如果已经处于同一个并查集中则不做操作。后续题目需要我们查询的是并查集的数量以及并查集中最大的节点数量
参考代码
前面都是并查集模板注意构造并查集的时候至少把节点数1因为用于实现的vetcor下标从0开始大部分题目的下标是从1开始的最后查询的时候利用set进行排序输出即可
#include bits/stdc.h
using i64 long long;struct DisjointSet {int _n;std::vectorint _fa,_size;DisjointSet(){}DisjointSet(int n){init(n);}void init(int n) {_fa.resize(n);std::iota(_fa.begin(),_fa.end(),0);_size.assign(n,1);}int find(int x) {if(x!_fa[x]) _fa[x] find(_fa[x]);return _fa[x];}bool same(int x,int y) {return find(x)find(y);}bool merge(int x,int y) {int fx find(x);int fy find(y);if(fx!fy) {_size[fy]_size[fx];_fa[fx] fy;return true;}return false;}
};
using pii std::pairint,int;int main() {std::cin.tie(nullptr)-sync_with_stdio(false);int n,k;std::cin n k;DisjointSet disjointSet DisjointSet(n1);for(int i 0;ik;i) {int mem1,mem2;std::cin mem1 mem2;disjointSet.merge(mem1,mem2);}std::setpii st;for(int i 1;in;i) {int t disjointSet.find(i);st.insert(std::make_pair(disjointSet._size[t],t));}std::cout st.size() (*st.rbegin()).first \n;return 0;
}4.3 1565: 并查集-团伙 思路
这个题由于enemy的存在需要多维护一个ene[]数组ene[]数组初始化为0如果遇到p等于0的时候分别判断x和y的ene是否为0如果为0则代表他们当前没有enemy则把ene值设置成对方即x和y分别属于两个并查集中如果当前存在ene那么就把自己合并到他们enemy的并查集中因为敌人的敌人是朋友。至于p等于1的情况当做正常并查集的合并来做。最后输出并查集的数量计算父节点等于自身的节点数量即可
参考代码
#include bits/stdc.h
using i64 long long;struct DisjointSet {int _n;std::vectorint _fa,_size;DisjointSet(){}DisjointSet(int n){init(n);}void init(int n) {_fa.resize(n);std::iota(_fa.begin(),_fa.end(),0);_size.assign(n,1);}int find(int x) {if(x!_fa[x]) {_fa[x] find(_fa[x]);}return _fa[x];}bool same(int x,int y) {return find(x)find(y);}bool merge(int x,int y) {int fx find(x);int fy find(y);if(fx!fy) {_size[fy]_size[fx];_fa[fx] fy;return true;}return false;}
};int main() {std::cin.tie(nullptr)-sync_with_stdio(false);int n,m;std::cin n m;DisjointSet disjointSet DisjointSet(n1);std::vectorint ene(n1,0);for(int i 0;im;i) {int t,x,y;std::cin t x y;if(t) {//enemyif(ene[x]) {disjointSet.merge(y,ene[x]);}else {ene[x] y;}if(ene[y]) {disjointSet.merge(x,ene[y]);}else {ene[y] x;}}else {//frienddisjointSet.merge(x,y);}}int ans 0;for(int i 1;in;i) {if(disjointSet.find(i)i) ans;}std::cout ans \n;return 0;
}4.4 1566: 并查集-打击犯罪 思路
题目有点反直觉我一开始想着从1到k依次进行判断断开某个关系后可以使得他们中最大的一个危险程度小于等于n/2然后后来发现写起来很困难。正难则反因此我们考虑从n开始循环跑到1结束每次循环让这个循环变量i这个节点和它有关系并且大于k的j节点进行合并然后看看是否有危险程度大于n/2的并查集即可。
参考代码
#include bits/stdc.h
using i64 long long;struct DisjointSet {int _n;std::vectorint _fa,_size;DisjointSet(){}DisjointSet(int n){init(n);}void init(int n) {_fa.resize(n);std::iota(_fa.begin(),_fa.end(),0);_size.assign(n,1);}int find(int x) {if(x!_fa[x]) {_fa[x] find(_fa[x]);}return _fa[x];}bool same(int x,int y) {return find(x)find(y);}bool merge(int x,int y) {int fx find(x);int fy find(y);if(fx!fy) {_size[fx]_size[fy];_fa[fy] fx;return true;}return false;}
};int main() {std::cin.tie(nullptr)-sync_with_stdio(false);int n;std::cin n;std::vectorstd::vectorint edges(n1,std::vectorint());DisjointSet disjointSet DisjointSet(n1);for(int i 0;in;i) {int siz;std::cin siz;for(int j 0;jsiz;j) {int t;std::cin t;edges[i1].emplace_back(t);}}for(int k n;k1;k--) {for(auto edge:edges[k]) {if(edgek) {disjointSet.merge(k,edge);}}if(disjointSet._size[disjointSet.find(k)]n/2) {std::cout k \n;return 0;}}return 0;
}4.5 1567: 并查集-搭配购买 思路
并查集01背包中间对数据的存储搞得我很头疼用了一堆vector先把c[]和d[]数组存起来做了并查集的合并后再算一个并查集c[]的总和sumc[]以及d[]的总和sumd[]然后把计算好的总和放进real_c[]和real_d[]数组中再使用一个dp[]数组做一遍01背包最后的dp[w]输出即可
参考代码
#include bits/stdc.h
using i64 long long;struct DisjointSet {int _n;std::vectorint _fa,_size;DisjointSet(){}DisjointSet(int n){init(n);}void init(int n) {_fa.resize(n);std::iota(_fa.begin(),_fa.end(),0);_size.assign(n,1);}int find(int x) {if(x!_fa[x]) {_fa[x] find(_fa[x]);}return _fa[x];}bool same(int x,int y) {return find(x)find(y);}bool merge(int x,int y) {int fx find(x);int fy find(y);if(fx!fy) {_size[fx]_size[fy];_fa[fy] fx;return true;}return false;}
};
using pii std::pairint,int;int main() {std::cin.tie(nullptr)-sync_with_stdio(false);int n,m,w;std::cin n m w;std::vectorint c,d;for(int i 0;in;i) {int tmpc,tmpd;std::cin tmpc tmpd;c.emplace_back(tmpc);d.emplace_back(tmpd);}DisjointSet disjointSet DisjointSet(n1);for(int i 0;im;i) {int x,y;std::cin x y;disjointSet.merge(x,y);}std::vectorint sumc(n1,0),sumd(n1,0);for(int i 1;in;i) {int t disjointSet.find(i);sumc[t] c[i-1];sumd[t] d[i-1];}std::vectorint real_c,real_d;for(int i 1;in;i) {if(sumc[i]!0) {real_c.emplace_back(sumc[i]);real_d.emplace_back(sumd[i]);}}std::vectorint dp(w1,0);for(int i 0;ireal_c.size();i) {for(int j w;jreal_c[i];j--) {dp[j] std::max(dp[j],dp[j-real_c[i]]real_d[i]);}}std::cout dp[w] \n;return 0;
}五、后记
剩下的题目及并查集的进一步运用求最小生成树的Kruskal算法见后续的2
