不相交集类

等价关系:自反性,对称性,传递性

class DisjSets//不相交集的类架构
{
public:
    explicit DisjSets(int numElements);
    int find(int x) const;
    int find(int x);
    void unionSets(int root1,int root2);
    void unionSets2(int root1,int root2);
private:
    vector<int> s;
};
DisjSets::DisjSets(int numElements) : s(numElements)//初始化
{
    for(int i=0 ; i < s.size() ; i++)
        s[i] = -1;
}
void DisjSets::unionSets(int root1,int root2)
{
    s[root2] = root1;
}
void DisjSets::unionSets2(int root1,int root2)
{
    if( s[root2] < s[root1])
        s[root1] = root2;
    else
    {
        if(s[root1] == s[root2])
            s[root1]--;
        s[root2] = root1;
    }
}
int DisjSets::find(int x) const
{
    if(s[x] < 0)
        return x;
    else
        return find(s[x]);
}

灵巧求并算法:按大小求并,或者按高度求并

路径压缩:唯一变化就是返回的是 find 返回的值(与按大小求并完全兼容)

int DisjSets::find(int x) 
{
    if(s[x] < 0)
        return x;
    else
        return s[x] = find(s[x]);
}

应用:迷宫问题

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 图m着色问题

    1 问题描述:   给定无向图,m种不同的颜色。使每一种着色法使G中每条边的2个顶点不同颜色,若一个图最少需要m种颜色才能使图中每条边连接的2个顶点着不同颜色,...

    用户1154259
  • cuda测试二维block的使用

    #include "cuda_runtime.h" #include <stdio.h> #include <stdlib.h> #include <math....

    用户1154259
  • 剑指OFFER之重建二叉树(九度OJ1385)

    题目描述: 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7...

    用户1154259
  • cf449D. Jzzhu and Numbers(容斥原理 高维前缀和)

    答案=任意一种方案 - 至少有\(1\)位为\(1\)的方案 + 至少有两位为\(1\)的方案 - 至少有三位为\(1\)的方案

    attack
  • POJ 2104 K-th Number(主席树)

    Description You are working for Macrohard company in data structures department...

    attack
  • codeforces415D. Glad to see you!

    交互库会返回$|x - a| <= |y - b| ? "TAK" : "NIE"$

    attack
  • 数据结构 图

    1-1 无向连通图至少有一个顶点的度为1 错误: 无向连通图考点: 1. 每条边连接两个顶点,所有顶点的度之和等于边数的2倍 2.记住两个特殊的无相连通图模型:...

    Kindear
  • 原 初学算法-快速排序与线性时间选择(De

    不高不富不帅的陈政_
  • LeetCode 第 210 场周赛 解题报告

    那么在遍历过程中,栈中元素数量的最大值即为答案。栈中的(可以理解为还没遍历到匹配的),即那些嵌套的(。

    ACM算法日常
  • 计算机二级大题.

    1题 #include <iostream> using namespace std; class MyClass { public: MyClass(...

    东风冷雪

扫码关注云+社区

领取腾讯云代金券