投稿
  1. 首页
  2. C

[AcWing算法提高课]之 高阶数据结构 并查集（C++题解）

code • 2022-5-16 • C • 阅读 17

[AcWing算法提高课]之 高阶数据结构 并查集（C++题解）,第1张

目录

（一）并查集的框架

（1）初始化并查集

（2）find函数实现路径压缩

（3）并查集的应用过程

（二）不带权重并查集例题

（1）亲戚

（2）格子游戏

（3）搭配购买

（4）程序自动分析

（三）带权重并查集（待补充）

（1）银河英雄传说

（一）并查集的框架 （1）初始化并查集 
const int N=1e5+10;
int p[N];
int Size[N];
int d[N];//x->其祖宗节点的距离不用初始化：全局变量默认为 0

void init()
{
    for(int i=1;i<=N;i++)
    {
        p[i]=i;//每个节点的初始祖宗节点就是自己
        Size[i]=1;//每个节点的初始子长度为1（即自己）
    }
}
（2）find函数实现路径压缩 
int find_without_weight(int x)
{
    if(x!=p[x]) p[x]=find_without_weight(p[x]);
    return p[x];
}

int find_with_weight(int x)
{
    if(p[x]!=x)
    {
        int root=find_with_weight(p[x]);//找根
        d[x]+=d[p[x]];//d[x]到根节点的距离=x->父节点的距离+父节点到根节点的距离
        p[x]=root;//记录x的根
    }
    return p[x];
}
（3）并查集的应用过程 
（1）根据题目所求，将所给的点进行拼接，即：
void test_without_weight()//不带权重
{
    int n;
    cin>>n;//执行n次 合并 *** 作

    while(n--)
    {
        int a,b;//要 *** 作的两个节点
        cin>>a>>b;
        int pa=find_without_weight(a);//寻找它们的各自的祖宗
        int pb=find_without_weight(b);

        p[pa]=pb;//将a节点的祖宗节点 连接到b的祖宗节点
    }
}

void test_with_weight()//带权重
{
    int n;
    cin>>n;

    while(n--)
    {
        int a,b;
        cin>>a>>b;

        int pa=find_with_weight(a);
        int pb=find_with_weight(b);

        d[pa]=Size[pb];//pa->pb的距离为 Size[pb]
        Size[pb]+=Size[pa];//合并：pb为根的 战舰列边长
        p[pa]=pb;
    }
}
（2）查询过程：
void query()
{
    int a,b;
    cin>>a>>b;

    int pa=find_without_weight(a);
    int pb=find_without_weight(b);

    if(pa!=pb) puts("Write what you want here");
    else puts("Write what you want here");
}

完整过程：

#include
#include
#include
using namespace std;

const int N=1e5+10;
int p[N];
int Size[N];
int d[N];//x->其祖宗节点的距离不用初始化：全局变量默认为 0

void init()
{
    for(int i=1;i<=N;i++)
    {
        p[i]=i;//每个节点的初始祖宗节点就是自己
        Size[i]=1;//每个节点的初始子长度为1（即自己）
    }
}

int find_without_weight(int x)
{
    if(x!=p[x]) p[x]=find_without_weight(p[x]);
    return p[x];
}

int find_with_weight(int x)
{
    if(p[x]!=x)
    {
        int root=find_with_weight(p[x]);//找根
        d[x]+=d[p[x]];//d[x]到根节点的距离=x->父节点的距离+父节点到根节点的距离
        p[x]=root;//记录x的根
    }
    return p[x];
}

void test_without_weight()
{
    int n;
    cin>>n;//执行n次 合并 *** 作

    while(n--)
    {
        int a,b;//要 *** 作的两个节点
        cin>>a>>b;
        int pa=find_without_weight(a);//寻找它们的各自的祖宗
        int pb=find_without_weight(b);

        p[pa]=pb;//将a节点的祖宗节点 连接到b的祖宗节点
    }
}

void test_with_weight()
{
    int n;
    cin>>n;

    while(n--)
    {
        int a,b;
        cin>>a>>b;

        int pa=find_with_weight(a);
        int pb=find_with_weight(b);

        d[pa]=Size[pb];//pa->pb的距离为 Size[pb]
        Size[pb]+=Size[pa];//合并：pb为根的 战舰列边长
        p[pa]=pb;
    }
}

void query()
{
    int a,b;
    cin>>a>>b;

    int pa=find_without_weight(a);
    int pb=find_without_weight(b);

    if(pa!=pb) puts("Write what you want here");
    else puts("Write what you want here");
}

int main()
{
    init();
    
    //输入

    test_without_weight();

    query();

    return 0;
}
（二）不带权重并查集例题 （1）亲戚

1249. 亲戚 - AcWing题库

#include
#include
#include
using namespace std;

const int N=2e4+10;
int n,m,q;
int p[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    scanf("%d %d",&n,&m);
    
    for(int i=1;i

最大的感受就是，我用cin 读一直超时，多组数据还是用 scanf 吧

（2）格子游戏

活动 - AcWing

核心思路：

（1）将二维坐标换成一维坐标，注意 get函数转换时要从0开始，才可以做这样的变形，而题目是从1开始的，所以，需要将x--,y--

（2）终止条件是：求出两个坐标的一维映射后，分别求出它们的祖先，如果它们的祖先相同，那么就证明，此时 a->b 连线的话，就会使得图形闭合，此时就是题目所求的答案了

（3）小细节：用char op[2]存 *** 作数，防止出现空格 回车 等情况恶心选手

#include
#include
#include
using namespace std;

const int N=200;
const int M=N*N;
int n,m;
int p[M];

int get(int x,int y)
{
    return x*n+y;
}

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    cin>>n>>m;
    for(int i=0;i
（3）搭配购买

活动 - AcWing

核心思路：

将组合的云朵的所有价值，价格联合，然后只对 根结点进行01背包

#include
#include
#include
using namespace std;

const int N=1e5+10;
int n,m,w;
int weight[N],val[N];
int p[N];
int f[N];

int find(int x)
{
    if(p[x]!=x) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    cin>>n>>m>>w;//n件物品，m个组合，w为容量
    for(int i=1;i<=n;i++) p[i]=i;
    for(int i=1;i<=n;i++) cin>>weight[i]>>val[i];
    
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        
        int pa=find(a);
        int pb=find(b);
        
        if(pa!=pb)
        {
            weight[pb]+=weight[pa];
            val[pb]+=val[pa];
            p[pa]=pb;
        }
    }
    
    for(int i=1;i<=n;i++)
    {
        if(p[i]==i)
        {
            for(int j=w;j>=weight[i];j--)
            {
                f[j]=max(f[j],f[j-weight[i]]+val[i]);
            }
        }
    }
    cout<
（4）程序自动分析

237. 程序自动分析 - AcWing题库

核心思路：

（1）离散化：

因为i，j的范围为10^9次方，而实际上只有 10^5条指令，因此顶多会用到 2*10^5个数字

因此就会存在空间上的浪费（实际上const int N=1e9 存并查集数组肯定是会爆的）

因此需要将空间进行优化：即用离散化，将 数字 i,j  用离散化的值存储，那么因为这里对数字的大小并没有要求（说白了，数字的大小这个性质在这里查询没有用，所以我们不需要排序 去重 二分 构造一个有序的离散化映射数组），因此只需初始化一个数字n，每当有一个数字需要离散化时，将n++即可后赋值到 映射数组

（2）将所有相等的情况 用并查集进行存储

（3）再次遍历 存离散化后的数组，如果遍历 到的两个数字关系是不相等，但是它们的祖宗节点相等那么就证明发生了冲突，此时就是true（确认已经发生了冲突），反之就是false（没有发生冲突）

#include
#include
#include
#include
#include
using namespace std;

const int N=2000010;
int n,m;
int p[N];
unordered_map S;

struct Query{//
    int x,y,e;
}query[N];

int get(int x)//无序 离散化
{
    if(S.count(x)==0) S[x]=++n;
    return S[x];
}

int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        n=0;
        S.clear();
        cin>>m;
        
        for(int i=0;i>x>>y>>e;
            query[i]={get(x),get(y),e};//离散化后 query数组存关系
        }
        
        for(int i=1;i<=n;i++) p[i]=i;//并查集初始化
        
        for(int i=0;i
（三）带权重并查集（待补充） （1）银河英雄传说

238. 银河英雄传说 - AcWing题库

核心思路：见注释

#include 
#include 
#include 
#include 
using namespace std;

const int N=300010;
int m;
int p[N],Size[N],d[N];

int find(int x)
{
    if(p[x]!=x)
    {
        int root=find(p[x]);//找根
        d[x]+=d[p[x]];//d[x]到根节点的距离=x->父节点的距离+父节点到根节点的距离
        p[x]=root;//记录x的根
    }
    return p[x];
}

int main()
{   
    cin>>m;

    for(int i=1;ipb的距离为 Size[pb]
            Size[pb]+=Size[pa];//合并：pb为根的 战舰列边长
            p[pa]=pb;
        }
        else
        {
            int pa = find(a), pb = find(b);
            if (pa != pb) puts("-1");
            else printf("%d\n", max(0, abs(d[a] - d[b]) - 1));
        }
    }


    return 0;
}

作者：lihua
链接：https://www.acwing.com/activity/content/code/content/3425829/
来源：AcWing
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/langs/914617.html

赞 (0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
code code 管理员组
0 0
上一篇 2022-05-16
下一篇 2022-05-16

发表评论

登录后才能评论

评论列表（0条）

Copyright © 2022 内存溢出 版权所有 湘ICP备2022025235号 Powered by outofmemory.cn

保存