怎么做一键添加信任网站,辽宁建设厅新网站,南昌手机网站,seo网络排名优化作者#xff1a;指针不指南吗 专栏#xff1a;算法篇 #x1f43e;或许会很慢#xff0c;但是不可以停下#x1f43e; 文章目录1.思想2.模板3.应用3.1 合并集合3.2 连通块中点的数量1.思想
并查集是一种树型的数据结构#xff0c;用于处理一些不相交集合的合并及查询问题… 作者指针不指南吗 专栏算法篇 或许会很慢但是不可以停下 文章目录1.思想2.模板3.应用3.1 合并集合3.2 连通块中点的数量1.思想
并查集是一种树型的数据结构用于处理一些不相交集合的合并及查询问题即所谓的并、查 比如说我们可以用并查集来判断 某个节点是否属于某棵树等。 并查集 将两个集合合并 询问两个元素是否在一个集合当中 基本原理 每个集合用一棵树来表示。 树根的编号就是整个集合的编号。 每个节点存储它的父节点p[x]表示x的父节点。 相关问题 如何判断树根if(p[x]x) 如何求x的集合编号while(p[x]!x) xp[x] 判断两个元素是否在一个集合里面即两个元素的编号相同find(p[x])find(p[y]) 如何合并两个集合px是x的集合编号py是y的集合编号。 p[x]y即让一个集合 a 的根节点指向另一个集合 b 的根节点把a直接插在b的根节点下面。 优化 路径压缩让每个节点都直接指向根节点祖先
2.模板
并查集的类型模板这里给出三种具体题目具体分析看看需要维护什么添加什么。
(1)朴素并查集
int p[N]; //存储每个点的祖宗节点// 返回x的祖宗节点
int find(int x)
{if (p[x] ! x) p[x] find(p[x]);return p[x];
}// 初始化假定节点编号是1~n
for (int i 1; i n; i ) p[i] i; //初始化每个元素的父节点和祖宗节点就是它本身// 合并a和 b所在的两个集合
p[find(a)] find(b); //让a的祖宗节点指向b的祖宗节点a树插在b根节点下面(2)维护size的并查集
int p[N], size[N];
//p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义表示祖宗节点所在集合中的点的数量// 返回x的祖宗节点
int find(int x)
{if (p[x] ! x) p[x] find(p[x]);return p[x];
}// 初始化假定节点编号是1~n
for (int i 1; i n; i )
{p[i] i;size[i] 1; //初始化每个集合里面只有一个元素
}// 合并a和b所在的两个集合
size[find(b)] size[find(a)]; //集合大小相加
p[find(a)] find(b);(3)维护到祖宗节点距离的并查集
int p[N], d[N];
//p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离// 返回x的祖宗节点
int find(int x)
{if (p[x] ! x){int u find(p[x]);d[x] d[p[x]];p[x] u;}return p[x];
}// 初始化假定节点编号是1~n
for (int i 1; i n; i )
{p[i] i;d[i] 0;
}// 合并a和b所在的两个集合
p[find(a)] find(b);
d[find(a)] distance; // 根据具体问题初始化find(a)的偏移量3.应用
3.1 合并集合 一共有 n 个数编号是 1∼n最开始每个数各自在一个集合中。 现在要进行 m 个操作操作共有两种 M a b将编号为 a 和 b 的两个数所在的集合合并如果两个数已经在同一个集合中则忽略这个操作Q a b询问编号为 a 和 b 的两个数是否在同一个集合中 输入格式 第一行输入整数 n 和 m。 接下来 m 行每行包含一个操作指令指令为 M a b 或 Q a b 中的一种。 输出格式 对于每个询问指令 Q a b都要输出一个结果如果 a 和 b 在同一集合内则输出 Yes否则输出 No。 每个结果占一行。 数据范围 1≤n,m≤10510^5105 输入样例 4 5
M 1 2
M 3 4
Q 1 2
Q 1 3
Q 3 4输出样例 Yes
No
Yes代码实现 #includebits/stdc.h
using namespace std;const int N100010;int n,m; //n表示点的数量m表示操作的次数
int p[N]; //存的每个节点的父节点int find(int x) //返回x的祖宗节点路径压缩
{if(p[x]!x) p[x]find(p[x]);return p[x];
}int main()
{scanf(%d%d,n,m);for(int i1;in;i) p[i]i; //最开始每个点都各自在一个集合中so父节点就是他本身while(m--){char op[2];int a,b;scanf(%s%d %d,op,a,b);//合并if(op[0]M) p[find(a)]p[find(b)]; //让a的祖宗节点等于b的祖宗节点让a的祖宗节点直接插在b祖宗节点下面else{if(find(a)find(b)) puts(Yes); //判断是否属于同一个集合else puts(No);} }return 0;
}注意
读入字母M或者是Q的时候使用字符串op[2],是因为直接用char的话可能会出现空格换行的问题作物这种比较保险记得在后面使用的时候用op[0],不能直接使用op
puts自动包含换行
3.2 连通块中点的数量 给定一个包含 n 个点编号为 1∼n的无向图初始时图中没有边。 现在要进行 m 个操作操作共有三种 C a b在点 a 和点 b 之间连一条边a 和 b 可能相等Q1 a b询问点 a 和点 b 是否在同一个连通块中a 和 b 可能相等Q2 a询问点 a 所在连通块中点的数量 输入格式 第一行输入整数 n 和 m。 接下来 m 行每行包含一个操作指令指令为 C a bQ1 a b 或 Q2 a 中的一种。 输出格式 对于每个询问指令 Q1 a b如果 a 和 b 在同一个连通块中则输出 Yes否则输出 No。 对于每个询问指令 Q2 a输出一个整数表示点 a 所在连通块中点的数量 每个结果占一行。 数据范围 1≤n,m≤10510^5105 输入样例 5 5
C 1 2
Q1 1 2
Q2 1
C 2 5
Q2 5输出样例 Yes
2
3思路 连通块就是一个点的集合集合中的点可以相互到达直接或者是间接都是可以的 这时候我们可以把它类比成一个树运用并查集一个点集合我们可以用一个编号来表示属于同一个编号就说明两个点之间可以相互到达在一个连通块里面 有三个操作 两点之间连一条边那么这两个点所在集合中的点都是可以相互到达的即合成一个连通块用并查集中的合并操作 判断是否在一个连通块用并查集的查询 询问一个点集合的数量需要我们额外维护初始化的时候每个集合1个合并的时候两个集合数量相加最后输出即可 代码实现 #includebits/stdc.husing namespace std;const int N1000010;
int n,m;
int p[N],sizel[N]; //p表示父节点sizel表示集合的大小记住sizel里面放的是祖宗节点后面容易出错int find(int n) //返回祖宗节点
{if(p[n]!n) p[n]find(p[n]);return p[n];
}int main()
{scanf(%d%d,n,m); //读入点的数量和操作的次数for(int i1;in;i){ //初始化父节点就是它本身集合大小都是1只有他自己p[i]i;sizel[i]1;}char op[5]; while(m--){scanf(%s,op); //读入操作的名字if(op[0]C){ //合并int a,b;scanf(%d%d,a,b);if(find(a)find(b)) continue; //相同则进入下个循环else{ //不同即操作两步的顺序不能反sizel[find(b)]sizel[find(a)]; //b的集合大小加上a的集合大小p[find(a)]find(b); //让a的祖宗节点指向b的祖宗节点}}else if(op[1]1){ //查询是否一个集合int a,b;scanf(%d%d,a,b);if(find(a)find(b)) puts(Yes);else puts(No);}else{if(op[1]2) { //输出集合大小int d;scanf(%d,d);printf(%d\n,sizel[find(d)]); }}}return 0;
}
