.la域名的门户网站网页大全

当前位置： 首页 > news >正文

.la域名的门户网站,网页大全,石家庄网站推广招聘,WordPress背景图片自适应目录 前言 一 并查集的思路 二 并查集的代码分析
三 实操我们的代码 四 并查集的代码优化 总结 前言 并查集主要是用来求解集合问题的#xff0c;用来查找集合还有就是合并集合#xff0c;可以把这个运用到最小生成树里面 一 并查集的思路 1 并查集的相关的操作… 目录 前言 一  并查集的思路 二  并查集的代码分析  三  实操我们的代码 四  并查集的代码优化 总结 前言 并查集主要是用来求解集合问题的用来查找集合还有就是合并集合可以把这个运用到最小生成树里面 一  并查集的思路 1  并查集的相关的操作      1  查找 函数find ( a )是用来查你需要查找的元素是在哪一个集合里面的      2  判断是否为同一个集合 函数issamset( a, b )是用来判断你输入的数字是否在同一个集合里面      3  合并两个集合 函数Iunion( a, b )是用来合并两个集合 2  并查集是怎么操作的 首先我们有很多个元素 首先可能不是很理解我来解释一下 就是我们要找这个元素在哪一个集合我没是不是很不好找因为名字啥的啥也没有 所以我没就要对这个集合进行命名才可以找到这个元素在哪里才可以进行下面的操作 所以最重要的就是给这个集合进行命名 ✅但是我们要怎么命名呢 我们只需要找到这个集合里面的代表元素就好了比如第一个集合的代表元素就是a ✅那么这个自环又是用来干什么的呢 这个自环就是为了方便我没找到那个代表的元素的你看我们找代表元素的时候是要利用遍历的所以当我们只有一个元素的时候我们就可以进行遍历遍历到自己了不就是自己就是代表元素么 ✅如何进行合并操作呢 首先我没看这个图就是我没在进行合并的时候我们先看这个元素个数的大小我没不难发现其实a和b都是一样的所以就是随便a在b的下面或者b在a的下面都可以最后b进行自环  ✅如果两个进行合并呢 首先我们可以看每个集合的元素的个数然后我们看都是2那么代价都是一样的所以我们可以b在d下面或者d在b下面注意是头部和头部进行连接别底部连接了那就是错的 ✅小挂大优化 小挂大的优化其实是用到这种一个比一个多的那么就是小的挂在大的下面 好了我们介绍完了理论部分接下来就是怎么用代码进行表示了 ✅过程的分析 那么我们先画一下图来理解一下 首先我们用一个头部数组father来表示他这个时候对应的头部是多少 用一个大小数组来表示这个时候这个集合有多大上面是初始化 0 1合并 首先0的头部变成1了但是1的头还是1但是这个0的大小没有改变是因为这个已经没用了用叉叉表示了因为此时0不是头了不再是代表数组 2 3合并 我们不难看到这个就是改变了头这个3的头变成3了 4 5合并 跟上述一样的  2 4合并 我们不难看出这个就是把这个对应不是代表值的直接标记为垃圾值 改变对应的头和大小就好了 1 5合并 最后我们就可以得出这个了 这个就是整个过程的分析  ✅扁平优化 然后其实这里面也有一个扁平优化就是在执行find的函数的时候经过的节点直接放到头部 类似于这个图就是我们经过的路的节点不再指向上一个节点直接指向头但是分支不是就是例如a的分支不会指向头除非经过它 扁平优化是一定要有的小挂大可以没有 二  并查集的代码分析  #includeiostream #includecstring #includealgorithmusing namespace std; const int N 1000010; //long int n;//deputy array int father[N]; //children size array int Isize[N]; //stack int stack[N];//lnitialize void bulid() {for (int i 1; i n;i) {father[i] i;Isize[i] 1;} }//find father way //里面有扁平化 int find(int x) {//沿途收集的点int Ssize 0;while (x ! father[x]) {//收集节点stack[Ssize] x;//继续往上走x father[x];}//扁平化//沿途已经收集好了x已经跳到对应节点了while (Ssize 0) {father[stack[–Ssize]] x;}return x; }//sameset way bool samset(int x, int y) {return find(x) find(y); }//union way void Iunion(int x,int y) {int fx find(x);int fy find(y);//小挂大的优化if (fx ! fy) {if (Isize[fx] Isize[fy]) {//fx 代表大小 //fy也是大小//在father数组里面改一下就是改了顶点Isize[fx] Isize[fy]; //modifty sizefather[fy] fx; //modifty father}else {Isize[fy] Isize[fx];father[fx] fy;}} }int main() {} 代码对应的旁边是有解析的读者可以看 我们来总结一下这个代码 首先我们有三个数组 1  father数组     2  size数组     3  stack数组 这三个数组分别用来存放头节点集合大小给find扁平化暂时放置元素 find函数在这里是尤为重要因为它涉及了扁平化和每个函数都需要用到它 1   bulid数组就是初始化size数组和father数组size用1初始化father就是数字了跟我上述说的思路是一样的 2   samset函数就是返回是否是一个集合只要看他们的头是不是一样的就好了直接return 他们头部是否相等就好了这个直接调用find函数 3   Iunion函数就是把这个数组取出来我们除了大小要改变还要改变头部我们可以用if语句来判断他们的头部是否相等这个需要用到find函数然后再进行大小化优化大的放到小的小面就好了这个也是用if语句进行判断 4   find数组就是查找了注意要用到扁平操作代码的操作的话就是我们需要用到一个栈来进行存储我们路上所经过的数字这个时候是不需要进行修改头部和大小的因为不是合并然后再进行扁平化操作把路径的元素都放出来连接到对应的头部 三  实操我们的代码 我们用一下我们上述的代码 这个是我们用上述代码进行实操的 代码的分析是跟上面一样的 #includeiostream #includecstring #includealgorithmusing namespace std; const int N 100001000; //long int n;//deputy array int father[N]; //children size array int Isize[N]; //stack int stack[N];//lnitialize void bulid() {for (int i 1; i n; i) {father[i] i;Isize[i] 1;} }//find father way //里面有扁平化 int find(int x) {//沿途收集的点int Ssize 0;while (x ! father[x]) {//收集节点stack[Ssize] x;//继续往上走x father[x];}//扁平化//沿途已经收集好了x已经跳到对应节点了while (Ssize 0) {father[stack[–Ssize]] x;}return x; }//sameset way bool samset(int x, int y) {return find(x) find(y); }//union way void Iunion(int x, int y) {int fx find(x);int fy find(y);//小挂大的优化if (fx ! fy) {if (Isize[fx] Isize[fy]) {//fx 代表大小 //fy也是大小//在father数组里面改一下就是改了顶点Isize[fx] Isize[fy]; //modifty sizefather[fy] fx; //modifty father}else {Isize[fy] Isize[fx];father[fx] fy;}} }int main() {int m;cin n m;bulid();while (m–) {int z, x, y;cin z x y;if (z 1) {Iunion(x, y);}else if (z 2) {if (samset(x, y)) {cout Y endl;}else {cout N endl;}}}return 0; } 四  并查集的代码优化 #includeiostream #includealgorithm #includecstringusing namespace std;const int N 1000000; int father[N]; int n;void build() {for (int i 0;i n;i) {father[i] i;} }int find(int x) {if (x ! father[x]) {//递归的操作学习过dfs都知道father[x] find(father[x]);}return father[x]; }bool semset(int x,int y) {return find(x) find(y); }void Iunion(int x, int y) {//不管大小集优化了father[find(x)] find(y); }int main() {} 这个代码的优化是用到了递归来解决的注意不需要size数组是因为大挂小是一个不必须的操作所以就不需要记录大小 判断是否在统一集合 跟之前讲述的一样还是用return进行返回 查找 这个就是要进行扁平化。就是我们在搜索的过程中直接进行操作而不是用一个stack进行存储这个操作是需要进行递归的就是在挖掘深度之后进行回溯的时候把上一个深度的值进行赋值然后最后在返回对应得头节点就好了 合并操作 这个也很简单就是把这个头给进行修改就好了但是你需要判断是谁合并谁先 总结 我们主要讲述了并查集 并查集为什么叫并查集呢 其实就是合并和查找在集合里面进行操作 然后我们涉及了几个功能就是查找合并判断是否在同一集合 这集合代码的实现和讲解在上面有