正文之前

前几天苦练图论，虽然还不算登堂入室？但是好歹还是懂了好几个概念，今天就讲讲我最开始认识的一个，很棒的检查图的连通性的算法--并查集！！！

正文

具体的想法来自一篇写的超好的博客，如果底子不是很好，建议看下面这篇，当然如果可以给我顺手点个赞就更好了！！

具体的代码如下：

#include
    
     using namespace std;// 定义全局变量，作为并查集！！ uf 取自：union find int uf[100]; //定义并查集的查找根节点的函数int Find_set(int x){    int s=x;    while(uf[s]!=s)        s=uf[s];    int d=x,j;//路径压缩算法    while(uf[d]!=d)    {        j=uf[d];        uf[d]=s;        d=j;    }    return s;}// 定义图的整合算法void mix(int x,int y){    int s=Find_set(x);    int d=Find_set(y);    if(s!=d)        uf[s]=d;}int main(){    int size,num_of_tuple,a,b,root_point;    cin>>size>>num_of_tuple;//初始化并查集数组    for (int i = 0; i < size; ++i)    {        uf[i]=i;    }// 进行路径的初始化    for (int i = 0; i < num_of_tuple; ++i)    {        cin>>a>>b;        mix(a,b);    }    for (int i = 0; i < size; ++i)    {        cout<<"第 "<
     <<" 个元素的父亲是："<
      
       <<" 根节点是： "<
       
        <
       
      
    

下面我来说说，这个东西是怎么一回事：

并查集本身是一个数组，每个元素都有自己的编号，也就是常用的下标， 每个下标对应的a[i] 都有一个数，这个数初始化的时候 是i ，但是之后 路径初始化的时候，我们进行扰乱。把每个下标对应的值，指向这个下标所表示的节点的父节点，层层叠叠 下来，最终就形成了一条通路。每一个节点都有自己的父节点与根节点，当然，对于最终的根节点来说，父节点与根节点都是自己,所以这才是根节点。根节点的选择没有依据，完全按照你的输入顺序不同而有不同的根节点，不过根节点不重要，我们需要的是验证图的连通性。比如我想检验 4 6 两个节点是否联通，那么我们只需要检查两个节点的根节点是不是一个就行了。因为一个联通的图里面是不会有两个根节点的，在图的整合过程中，两个不联通的图，通过mix算法整合。也就是说一个根节点放弃了自己根节点的身份，成为另一个根节点的子节点。所以只要是联通的图，就会只存在一个根节点，如果两个子节点的最终根节点不相等，可以肯定的是：这两个子节点不在同一个图内，就检查了连通性了！！

（PS: 盗图狗走一波）

还有一个就是路径的压缩。当我们的一个子节点检查到自己父节点还有父节点的时候，这个子节点就循循善诱的找到自己的根节点，然后直接管根节点叫爸爸，把自己原来的父节点彻底抛弃。所有的节点都这么干，最后每个联通的图就成了一个菊花状的连通图了！！

正文之后

今天下午就是CCF CSP第十二届计算机能力资格认证考核了。。好激动，四个小时，不知道能拿多少分？既然可以带纸质资料，那我就把《C++ Primer》 《算法竞赛入门经典训练指南》带进去，然后把我写的那些代码全部打印出来带过去吧！毕竟那么多呢！现在就好好的整理吧~ 待会一点出发去打印，一点半考试，时间上应该来得及~~