TYS的博客

算法小白努力学习中

0%

可持久化并查集

发表于 更新于

可持久化并查集

可持久化并查集 = 可持久化 + 并查集 = 主席树 + 并查集

leetcode 1724 检查边长度限制的路径是否存在 II

主席树方便用来维护历史的版本信息，可以支持回退， 访问之前版本的数据结构。

并查集，常用的两种优化方法是路径压缩，按秩合并。在可持久化并查集中只会用到按秩合并，即深度小的点向深度大的点合并，保证单次查询的时间复杂度为$ologn$

  • 可持久化并查集进本操作，状态定义
1
2
3
4
int tot;
int rt[N] // 保存每一个版本的头结点
int ls[N << 5], rs[N << 5] // 每个节点的左右孩子
int fa[N << 5], sz[N << 5] // 节点的父亲、树的高度

  • 建立基础主席树

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    void build(int &t, int l, int r) {
    	t = ++tot;
    	if (l == r) {
    		fa[t] = l;
    		return;
    	}
    	int mid = l + (r - l) / 2;
    	build(ls[t], l, mid);
    	build(rs[t], mid + 1, r);
    }

  • 查找某一个元素在主席树中的下标

    1
    2
    3
    4
    5
    6
    7
    int query(int t, int l, int r, int x) {
        // t为某一历史版本的根节点下标， x为待查找的元素
    	if (l == r) return t;
    	int mid = l + (r - l) / 2;
    	if (x <= mid) return query(ls[t], l, mid, x);
    	else return query(rs[t], mid + 1, r, x);
    }

  • 查找版本号为t元素x的祖先

    1
    2
    3
    4
    5
    int find(int t, int l, int r, int x) {
    	int p = query(t, l, r, x); // 查询x的下标
    	if (fa[p] == x) return x;
    	return find(t, l, r, fa[p]);
    }

  • 按秩合并

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    int unite(int pre, int l, int r, int x, int father) {
        // 修改x节点的父亲为father
        int t = ++tot;
        ls[t] = ls[pre], rs[t] = rs[pre];
        if (l == r) {
            fa[t] = father;
            sz[t] = sz[pre];
            return t;
        }
        int mid = l + (r - l) / 2;
        if (x <= mid) ls[t] = unite(ls[pre], l, mid, x, father);
        else rs[t] = unite(rs[pre], mid + 1, r, x, father);
        return t;
    }

  • 更新合并后父节点的深度

    1
    2
    3
    4
    5
    6
    7
    8
    9
    void update(int t, int l, int r, int x) {
    	if (l == r) {
    		sz[t]++;
    		return;
    	}
    	int mid = l + (r - l) / 2;
    	if (x <= mid) update(ls[t], l, mid, x);
    	else update(rs[t], mid + 1, r, x);
    }

  • 全部代码如下, java用时329ms通过了全部测试用例， 但是用c++超时了…..不开o2优化太坑人了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#pragma GCC optimize(2)
class DistanceLimitedPathsExist {
public:
    static constexpr int N = 10005;
    int tot, n;
    int rt[N], ls[N << 5], rs[N << 5], fa[N << 5], sz[N << 5];
    vector<int> dis;

    void build(int &t, int l, int r) {
        t = ++tot;
        if (l == r) {
            fa[t] = l;
            return;
        }
        int mid = l + (r - l) / 2;
        build(ls[t], l, mid);
        build(rs[t], mid + 1, r);
    }

    int query(int t, int l, int r, int x) {
        if (l == r) return t;
        int mid = l + (r - l) / 2;
        if (x <= mid) return query(ls[t], l, mid, x);
        else return query(rs[t], mid + 1, r, x);
    }

    int find(int t, int l, int r, int x) {
        int p = query(t, l, r, x); 
        if (fa[p] == x) return p;
        return find(t, l, r, fa[p]);
    }

    int unite(int pre, int l, int r, int x, int father) {
    // 修改x节点的父亲为father
        int t = ++tot;
        ls[t] = ls[pre], rs[t] = rs[pre];
        if (l == r) {
            fa[t] = father;
            sz[t] = sz[pre];
            return t;
        }
        int mid = l + (r - l) / 2;
        if (x <= mid) ls[t] = unite(ls[pre], l, mid, x, father);
        else rs[t] = unite(rs[pre], mid + 1, r, x, father);
        return t;
    }

    void update(int t, int l, int r, int x) {
        if (l == r) {
            sz[t]++;
            return;
        }
        int mid = l + (r - l) / 2;
        if (x <= mid) update(ls[t], l, mid, x);
        else update(rs[t], mid + 1, r, x);
    }


    DistanceLimitedPathsExist(int n, vector<vector<int>>& edgeList) {
        tot = 0;
        this->n = n;
        memset(rt, 0, sizeof(rt));
        memset(ls, 0, sizeof(ls));
        memset(rs, 0, sizeof(rs));
        memset(fa, 0, sizeof(fa));
        memset(sz, 0, sizeof(sz));
        sort(edgeList.begin(), edgeList.end(), [](auto a, auto b) {
            return a[2] < b[2];
        });
        build(rt[0], 0, n - 1);
        for (int i = 0; i < edgeList.size(); ++i) {
            rt[i + 1] = rt[i];
            int x = edgeList[i][0], y = edgeList[i][1];
            int posx = find(rt[i], 0, n - 1, x), posy = find(rt[i], 0, n - 1, y);
            if (fa[posx] != fa[posy]) {
                if (sz[posx] > sz[posy]) swap(posx, posy);
                rt[i + 1] = unite(rt[i], 0, n - 1, fa[posx], fa[posy]);
                if (sz[posx] == sz[posy]) update(rt[i + 1], 0, n - 1, fa[posy]);
            }
            dis.push_back(edgeList[i][2]);
        }
    }
    
    bool query(int p, int q, int limit) {
        int num = upper_bound(dis.begin(), dis.end(), limit - 1) - dis.begin();
        int version = rt[num];
        int posx = find(version, 0, n - 1, p);
        int posy = find(version, 0, n - 1, q);
        if (fa[posx] == fa[posy]) return true;
        else return false;
    }
};