社区讨论
带权并查集、按秩合并和启发式合并(按大小合并)的疑问
学术版参与者 3已保存回复 2
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 2 条
- 当前快照
- 1 份
- 快照标识符
- @lo3ccu6l
- 此快照首次捕获于
- 2023/10/24 04:19 2 年前
- 此快照最后确认于
- 2023/10/24 04:19 2 年前
rt,带权并查集可以使用按秩合并或者启发式合并吗?我写的按秩只能过两个点。。。
本地栈空间只有2M,数据点成链会爆栈
银河英雄传奇
WA代码:
CPP#include <algorithm>
#include <cstdio>
#include <iostream>
using namespace std;
// 1.存前缀dis(前方战舰数量 即到祖先的路径长)
// 路径压缩返回时 给每个加1
// 2.总个数cnt
typedef const int cint;
cint maxj = 30001;
int fa[maxj];
int dis[maxj]; // 存储到祖先的距离
int cnt[maxj]; // 存储元素个数
int dep[maxj]; // 存储树深度 避免成链
int t;
int find(cint& x) {
if (fa[x] == x) return x;
// 存 当前到自己祖先的距离 + 祖先到新祖先的距离
// 记得暂存自己的祖先节点 要不然递归回来找不到
int f = find(fa[x]);
dis[x] += dis[fa[x]];
return fa[x] = f;
}
// 要保证合并的时候 不能单一顺序!!!
// 尤其不能加 if (fx < fy) swap(fx, fy);
// 小心爆栈!!!
/*
solution————按秩合并
用rank[ ]数组来记录每个根结点对应的树的深度
(如果不是根结点存以当前节点的子树的深度)
一开始,把所有元素的rank设为1,即自己就为一颗树,且深度为1;
合并的时候,比较两个根结点,把rank较小者合并到较大者中去。
*/
void merge(cint& x, cint& y) {
int fx = find(x), fy = find(y);
// x族的新祖先为fy 更新x族原祖先的数值 以便在find中传递
if (fx != fy) {
if (dep[fx] < dep[fy]) {
// 将fx(较小者)合并到fy(较大者)
dis[fx] += cnt[fy];
cnt[fy] += cnt[fx];
// cnt[fx]不用维护
// cnt[fx] = 0;
fa[fx] = fy;
} else {
dis[fy] += cnt[fx];
cnt[fx] += cnt[fy];
fa[fy] = fx;
}
if (dep[fx] == dep[fy]) {
dep[fx]++;
}
}
}
void init() {
for (int i = 1; i < maxj; i++) {
fa[i] = i;
cnt[i] = 1;
dep[i] = 1;
}
}
int main() {
ios::sync_with_stdio(0);
#ifndef ONLINE_JUDGE
freopen("E.P1196_1.in", "r", stdin);
#endif
init();
cin >> t;
while (t--) {
char op;
int i, j;
cin >> op >> i >> j;
if (op == 'M') {
// Merge
merge(i, j);
} else {
int fi = find(i), fj = find(j);
if (fi == fj) {
cout << abs(dis[i] - dis[j]) - 1 << endl;
// 不算两端点!
} else {
cout << -1 << endl;
}
}
}
return 0;
}
上面俩答案是29998
回复
共 2 条回复,欢迎继续交流。
正在加载回复...