并查集

并查集

Solost

2023 年 03 月 15 日

274 次浏览

暂无评论

214字数

ACM笔记

~~~cpp
(1)朴素并查集：

int p[N]; //存储每个点的祖宗节点

// 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

// 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ ) p[i] = i;

// 合并a和b所在的两个集合：
    p[find(a)] = find(b);

(2)维护size的并查集：

int p[N], size[N];
    //p[]存储每个点的祖宗节点, size[]只有祖宗节点的有意义，表示祖宗节点所在集合中的点的数量

// 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

// 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        size[i] = 1;
    }

// 合并a和b所在的两个集合：
    size[find(b)] += size[find(a)];
    p[find(a)] = find(b);

(3)维护到祖宗节点距离的并查集：

int p[N], d[N];
    //p[]存储每个点的祖宗节点, d[x]存储x到p[x]的距离

// 返回x的祖宗节点
    int find(int x)
    {
        if (p[x] != x)
        {
            int u = find(p[x]);
            d[x] += d[p[x]];
            p[x] = u;
        }
        return p[x];
    }

// 初始化，假定节点编号是1~n
    for (int i = 1; i <= n; i ++ )
    {
        p[i] = i;
        d[i] = 0;
    }

// 合并a和b所在的两个集合：
    p[find(a)] = find(b);
    d[find(a)] = distance; // 根据具体问题，初始化find(a)的偏移量

~~~

最后修改：2023 年 03 月 15 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

2023年中国高校计算机大赛-团队程序设计天梯赛（GPLT）上海理工大学校内选拔赛（同步赛) -F-坐火车

树状数组

动态规划

Codeforces Round 712 (Div. 1) - B. 3-Coloring

2023牛客寒假算法基础集训营2 L-Tokitsukaze and Three Integers

树状数组

AcWing - 1488. 最短距离

typecho个人博客更换服务器

电脑远程唤醒

夕阳西下

并查集

发表评论 取消回复 使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款

并查集

发表评论取消回复
使用cookie技术保留您的个人信息以便您下次快速评论，继续评论表示您已同意该条款