社区讨论

带权并查集、按秩合并和启发式合并(按大小合并)的疑问

学术版参与者 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 条回复,欢迎继续交流。

正在加载回复...