并查集
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. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载
声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性