湖南省网站备案登记wordpress网站建设公司

湖南省网站备案登记,wordpress网站建设公司,网站制作需求分析,重庆网站建设慕枫一、背景 1.并查集可解决的问题：并查集常用来解决连通性问题。也就是说当我们需要判断两个元素是否在同一个集合里的时候，就想到要用并查集。 2.并查集的功能： （1）将两个元素添加到一个集合中。 （2）判断两个元素在不在同一个集合。 二、原理：从代码层面上讲，如何…一、背景1.并查集可解决的问题：并查集常用来解决连通性问题。也就是说当我们需要判断两个元素是否在同一个集合里的时候，就想到要用并查集。2.并查集的功能：（1）将两个元素添加到一个集合中。（2）判断两个元素在不在同一个集合。二、原理：从代码层面上讲，如何将两个元素添加到同一个集合中？1.错误想法：（1）放到同一个数组或者set或者map中，这样就表示两个元素在同一个集合（但是这么多元素分门别类，可不止一个集合，可能是成百上千个集合，这时会定义很多的数组，不好实现）。（2）定义一个二维数组（但是如果要判断两个元素是否在同一个集合的时候，只能把二维数组都遍历一遍；每当想添加一个元素到某集合的时候，依然需要把二维数组都遍历一遍，才知道要放到哪个集合里，代码实现逻辑非常复杂）。2.正确思路：（1）将三个元素A,B,C（分别是数字）放在同一个集合，其实就是将三个元素连通在一起，如何连通？只需要用一个一维数组来表示，即：father[A] = B,father[B] = C，这样就能表述A与B与C连通了（有向连通图）。代码如下所示：// 将v，u 这条边加入并查集 void join(int u, int v) { u = find(u); // 寻找u的根 v = find(v); // 寻找v的根 if (u == v) return; // 如果发现根相同，则说明在一个集合，不用两个节点相连直接返回 father[v] = u; }（2）find函数的寻根过程，就是通过数组下标找到数组元素，然后一层一层地寻根，代码如下所示。// 并查集里寻根的过程 int find(int u) { if (u == father[u]) return u; // 如果根就是自己，直接返回