并查集

//对并查集专题，对其进行总结

1.基础知识

//p[x]函数
//用来储存父节点，其根本是帮助寻找祖宗节点
for(int i=1;i<=n;i++)p[i]=i;//初始化

//find函数
//找寻祖宗用来
int find(int x){
    if(p[x]!=x)
        p[x]=find(p[x]);
    return p[x];
}

2.基本操作

//初始化
for(int i=1;i<=n;i++)p[i]=i;//根据具体情况加上集合个数,权值等

//集合合并(祖宗相认)
p[find(x)]=find(y);

//查询是否为一个集合
if(find(x)==find(y)) cout<<"YES";
else cout<<"NO";

//集合中元素个数查询
for(int i=1;i<=n;i++){p[i]=i;size1[i]=1;}   //每个个数初始化为1
scanf("%d %d",&a,&b);               
if(find(a)==find(b))continue;   //避免重复相加
size1[find(b)]+=size1[find(a)];     //注意其顺序是先个数相加，再集合合并，反了会导致集合个数*2
p[find(a)]=find(b);
printf("%d",find(a));//具体查询时查询根节点中的个数才有效

//集合的个数查询
//当采用的是点亮模式(即说其启用才能启用，记的设置变量标记)
//遍历集合，父节点是其本身的是集合祖宗，祖宗个数即集合个数
for(int i=1;i<=n;i++)
if(p[x]==x)cnt++;

难点(带权并查集)

//求最短路径（较易）
struct node{            //设置路径,储存长度，和左右节点
    int x,y,w;
}a[5007];
int un(int x,int y){    //合并，思路是如果新加入的路径，两点都在集合则去除他
    int fx=find(x);
    int fy=find(y);
    if(fx!=fy)
    {
        p[fx]=fy;
        return 1;
    }
    return 0;
}
bool cmp(node a,node b){    //必不可少的步骤，让比较node节点转换为比较node.w(即为权值)
return a.w<b.w;             //本身node比较是无法比较的
}
主函数
利用sort(a+1,a+m+1,cmp)排序所有路径，对其有两边没标记的点，根据排序后的进行录入
一个n个节点的要录入n-1条路径


//利用对与根节点关系对其进行维护 ,对find函数进行了改变

    int find(int x)
{
    if(p[x] != x)
    {
        int tmp = find(p[x]);
        d[x] += d[p[x]]; //先计算该点到根节点的距离，也可与说与更节点的关系
        p[x] = tmp;     //压缩路径
    }
    return p[x];
}
//之后也是根据具体情况对合并时或其他对权值等进行维护

相关题目
链接https://vjudge.net/contest/429801#problem/D
    https://vjudge.net/problem/POJ-1182

优化方法

/*路径压缩:每一个执行find操作的时候,把访问过的节点(也就是所有元素的父亲),都统统指向树根祖宗
这种方法可以避免出题人刻意卡掉链式结构.时间复杂度O(logn)*/
//优化后找根节点复杂度为o(1)
int find(int x)
{
    return x==p[x]?x:p[x]=find(p[x]);//x==p[x]即为祖宗节点,不用优化,否则需要将其父节点直接优化到祖宗
}
//与我们的find函数是一样的

#### 总结
这类问题一般都把问题追随于根节点上，权值都加于根节点，且设立点与根节点的关系，（可以根据每个点到根节点距离表示每个点与根节点的关系）