【第十四课】并查集(acwing-836合并集合 / 做题思路 /c++代码)

目录

错误思路(但能骗分emm)--邻接矩阵(可以跳过)

思路

存在的问题

代码如下

并查集

思路

代码如下

?一些解释

---

错误思路(但能骗分emm)--邻接矩阵(可以跳过)

思路

刚看到这道题我自己做的时候，因为之前学的trie树的时候意识到使用二维数组的含义，所以在思考这道题的时候也更偏向于使用二维数组。

于是经过不断试错，就想出来了个这种做法：原理就是--图中的邻接矩阵，把输入的两个集合编号当作二维数组的下标，执行过M操作的两个集合编号对应的下标会更改为1，"代表"这两个集合合并了，为满足题意我们使用if语句，当两个集合已经执行过"合并"操作，就break。对于Q操作，我们直接判断输入的两个集合编号在二维矩阵中对应的数是否是1就ok了。

这样我们表面上能够实现部分"合并"操作，某些情况下输入输出是符合题意且正确的。

存在的问题

然而这种方法

第一：他其实并没有真正的完成M合并操作，与题意并不相符。

第二：由于我们创建了二维数组，题目要求n的数据范围最大是1e5，我们知道二维矩阵创建应该是n*n的，首先要创建一个1e5*1e5的二维数组本来在大部分计算机上就实现不了，超过了系统可用的内存量；其次我们数组元素是整型int，在32位系统中，其最大索引2.1×10^9，而二维数组元素最多有10^10，从这方面来讲也是不可行的( 在64位系统中，最多可有9.2*10^18，不存在该问题)。

于是我们只能缩小N的取值为1e3，这就已经减少了很多答案。

其实关于邻接矩阵创建二维数组的问题在图的学习中我们已经说过，由于二维数组使用到的坐标可能很少，空间浪费比较严重，我们当时就提出了邻接表的写法。我这里懒得折腾了，就没再思考那一种写法了(doge)。?

附数组内存大小限制的因素：?

第三：关于用这种方法得到错误结果的例子：

如果我们执行下面三个操作

M 1 2
M 2 3
Q 1 3

按照我们上面的思路：输出结果会是No。但其实我们首先将1和2合并到同一个集合中，然后将2和3合并到同一个集合中。1、2和3应该都在同一个集合中。

对于第三个原因，在后面使用并查集的代码进行操作时其实结果也是No，因此暂不深入讨论该因素。

因此这种方法是错误的。

代码如下

这里给出按照这种思路能够正确执行的代码?

#include<iostream>
#include<cstring>//引头文件
using namespace std;
const int N=1e3+10;
int p[N],s[N][N],n,m;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }
    char op[2];
    while(m--)
    {
        scanf("%s",op);
        int a=0,b=0;
        if(strcmp(op,"M")==0)//对于字符串的比较要用到strcmp函数
        {
            cin>>a>>b;
            if(s[a][b]==1)break;
            else s[a][b]=1;
        }
        else if(strcmp(op,"Q")==0){
            cin>>a>>b;
            bool ans=s[a][b];
            if(ans==1)printf("Yes\n");
            else printf("No\n");
        }
    }
    return 0;
}

关于这种方法的正确率什么的我也不是很清楚，只当一种下下策把。?

并查集

其实刚看到这道题，我对这道题题意有一些困惑：合并集合之后的两个集合何去何从了呢？最后他们是都放进了a还是b里呢？另一个集合里面难道是空了么？如果合并之后只会留下一个集合，那么留下两个中的某一个有什么影响呢？还有如果这两个集合里有重复元素怎么办呢？不需要考虑么？

感觉我在题意理解上真是，，，哎

下面是bing的一些解释

思路

我们先明确要实现的两个操作：M 合并两个集合 Q 查询两个集合是否已经合并

我们先想复杂的做法(我甚至这个都没想到😂)：怎么实现Q？判断这两个元素是不是在同一个集合里p[x]==p[y]，用一个数组p来表示每个元素所属的集合；怎么实现M呢?把其中一个集合里面的所有元素的所属集合也就是p数组的值都更改为另一个数组。

Q操作还好，M操作简直是太麻烦了，集合里万一有好多元素呢？怎么一个一个改？

于是我们就想到并查集这种算法：我们用树来表示每个集合，树根的编号就是集合编号。每个节点的元素都存储他的父节点，这个节点的下标代表这个元素本身。

利用这种方式来实现我们的M和Q操作：M操作就是利用while循环找到两个元素所在树的树根 (判断方式是p[x]==x，我们规定根节点的父节点为其自己)，然后将其中一个的p[x]指向另一个元素的父节点即可，也就是直接把这个集合这棵树直接连到另一棵树上。

关于其中找父节点的过程可以进行优化：当我们找到了一个节点的根节点，那么从根节点到该元素路径上的所有节点的p[x]都应赋值为根节点x，这样就避免了多次重复查找根节点。这也就是我们常说的路径压缩。

代码如下

#include<iostream>
using namespace std;
const int N=1e5+10;
int n,m;
int p[N];
int find(int x)
{
    if(p[x]!=x)p[x]=find(p[x]);//路径压缩
    return p[x];//返回根节点 也就是集合编号
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        p[i]=i;
    }
    while(m--)
    {
        char op[2];
        int a,b;
        scanf("%s%d%d",op,&a,&b);
        if(op[0]=='M')p[find(a)]=find(b);//这里是用一个字符型元素比较的因此可以直接==比较
        else {
            if(find(a)==find(b))printf("Yes\n");
            else printf("No\n");
        }
    }
}

?一些解释

1.op的 if 比较

在上面邻接矩阵的方法里我直接让op这一整个字符数组(即字符串)都与字母进行比较

strcmp(op,"M")==0

注意字符串的比较只能用strcmp函数，不可以直接用== 。补充strcmp函数两个字符串相等返回0，前者小于后者，返回<0的数..。

而在这里，我们直接将op数组第一个元素也就是op[0]与一个字符进行比较，这里就可以直接使用==啦

这个之前好像遇到过很多次了，要记住！

2.puts函数输出

在这里我用了printf函数进行输出，需要写的很多。但是puts函数就可以直接简化书写

if(find(a)==find(b))puts("Yes");
    else puts("No");

这是因为?puts 会自动将换行符 （'\n'） 附加到输出中，可以使代码更简洁，并减少忘记包含换行符的机会。简化语法书写。

3.递归函数find

由于我们的优化是，寻找其中一个节点的根节点，那么每次都会不断地向上搜索，而这中间搜索到的节点，也就是从根节点到该元素路径上的所有节点其根节点都是该元素的根节点，都直接赋值为最终的结果。也就达到了优化效果。

如果并未找到根节点(递归出口)，就不断执行p[x]=find(p[x]) (递归内容)。还记得递归函数的这两个要素吧~

4.关于传递性

关于这个样例，，，也试了其他博主的博客的代码，执行结果还是No，我也不是很确定关于其传递性的说法了，欢迎指点！！

4 3
M 1 2
M 2 3
Q 1 3
No

---

好啦并查集就先写到这里，有问题欢迎指出！

期末周也过去了，就好好学算法吧。这几天会先玩一下[😂]希望回来之后是每天日更！！

一起加油！！