并查集

struct DSU {
    vector<int> fa, rk;

    explicit DSU(int n) :fa(n + 1), rk(n + 1) {
        for (int i = 1;i <= n;i++)
            fa[i] = i;
    }

    void init(int n) {
        for (int i = 1;i <= n;i++)
            fa[i] = i, rk[i] = 0;
    }

    int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }

    bool same(int x, int y) { return find(x) == find(y); }

    void merge(int x, int y) {
        if (same(x, y)) return;
        int px = fa[x], py = fa[y];
        if (rk[px] > rk[py]) fa[py] = px;
        else if (rk[px] < rk[py]) fa[px] = py;
        else fa[px] = py, rk[py]++;
    }
};
///并查集(路径压缩+按秩合并),O(nα(n)),用于维护集合关系

带权并查集

template<class T>
struct DSU {
    vector<int> fa;
    vector<T> w;

    explicit DSU(int n) :fa(n + 1), w(n + 1, T::e()) {
        for (int i = 1;i <= n;i++)
            fa[i] = i;
    }

    void init(int n) {
        for (int i = 1;i <= n;i++)
            fa[i] = i, w[i] = T::e();
    }

    int find(int x) {
        if (fa[x] == x) return x;
        int pre = fa[x];
        fa[x] = find(fa[x]);
        w[x] = w[x] + w[pre];
        return fa[x];
    }

    bool same(int x, int y) { return find(x) == find(y); }

    bool merge(int x, int y, T _w) {
        if (same(x, y)) return w[x] + -w[y] == _w;
        int px = fa[x], py = fa[y];
        fa[px] = py;
        w[px] = -w[x] + _w + w[y];
        return true;
    }//注意方向,x合并到y
};
///带权并查集(路径压缩),O(nlogn),用于维护集合带权关系

struct T {
    double rate;
    static T e() { return T{ 1.0 }; }
    friend T operator+(const T &a, const T &b) { return T{ a.rate * b.rate }; }
    friend T operator-(const T &a) { return T{ 1 / a.rate }; }
    friend bool operator==(const T &a, const T &b) { return abs(a.rate - b.rate) < 1e-6; }
};
///权元封装类,需要定义合并(+),逆元(-),相等(==)的操作

原文地址:http://www.cnblogs.com/BlankYang/p/16929752.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性