1724. 检查边长度限制的路径是否存在 II 并查集_力扣1724

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

一张有 n 个节点的无向图以边的列表 edgeList 的形式定义，其中 edgeList[i] = [ui, vi, disi] 表示一条连接 ui 和 vi ，距离为 disi 的边。注意，同一对节点间可能有多条边，且该图可能不是连通的。

实现 DistanceLimitedPathsExist 类：

• DistanceLimitedPathsExist(int n, int[][] edgeList) 以给定的无向图初始化对象。
• boolean query(int p, int q, int limit) 当存在一条从 p 到 q 的路径，且路径中每条边的距离都严格小于 limit 时，返回 true ，否则返回 false 。

示例 1:

输入：
["DistanceLimitedPathsExist", "query", "query", "query", "query"]
[[6, [[0, 2, 4], [0, 3, 2], [1, 2, 3], [2, 3, 1], [4, 5, 5]]], [2, 3, 2], [1, 3, 3], [2, 0, 3], [0, 5, 6]]
输出：
[null, true, false, true, false]

解释：
DistanceLimitedPathsExist distanceLimitedPathsExist = new DistanceLimitedPathsExist(6, [[0, 2, 4], [0, 3, 2], [1, 2, 3], [2, 3, 1], [4, 5, 5]]);
distanceLimitedPathsExist.query(2, 3, 2); // 返回 true。存在一条从 2 到 3 ，距离为 1 的边，
                                          // 这条边的距离小于 2。
distanceLimitedPathsExist.query(1, 3, 3); // 返回 false。从 1 到 3 之间不存在每条边的距离都
                                          // 严格小于 3 的路径。
distanceLimitedPathsExist.query(2, 0, 3); // 返回 true。存在一条从 2 到 0 的路径，使得每条边的
                                          // 距离 < 3：从 2 到 3 到 0 行进即可。
distanceLimitedPathsExist.query(0, 5, 6); // 返回 false。从 0 到 5 之间不存在路径。

提示：

• 2 <= n <= 1e4
• 0 <= edgeList.length <= 1e4
• edgeList[i].length == 3
• 0 <= ui, vi, p, q <= n-1
• ui != vi
• p != q
• 1 <= disi, limit <= 1e9
• 最多调用 1e4 次 query 。

 来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/checking-existence-of-edge-length-limited-paths-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

 成功，开始写了两种，在线和离线，然后发现有人提到快照，按照快照又写了一遍

方法1：在线

简单的说就是一次一个并查集。才1e4随便玩，每次重开一个并查集即可。

1.按边权排序

2. 每次查询重置并查集，然后把边权小于目标的进行链接

3. 并查集判断是否有连起来

 class DistanceLimitedPathsExist {
            int[] parent;
            int[] size;
            int n;
            int[][] edgeList;
        public DistanceLimitedPathsExist(int n, int[][] edgeList) {
            Arrays.sort(edgeList,(a,b)->a[2]-b[2]);
            parent = new int[n];
            size = new int[n];
            this.n = n;
            this.edgeList = edgeList;
        }
 
        private int root(int a){
            return parent[a]==a?a:root(parent[a]);
        }
 
        private void connect(int a, int b){
            int ra = root(a);
            int rb = root(b);
            if(ra==rb) return;
            if(size[ra]>size[rb]){
                size[ra]+=size[rb];
                parent[rb] = ra;
            }else{
                size[rb]+=size[ra];
                parent[ra] = rb;
            }
        }
 
 
        public boolean query(int p, int q, int limit) {
            for(int i = 0; i < n; i++){
                parent[i] = i;
                size[i] = 1;
            }
 
            for(int i = 0;i < edgeList.length && edgeList[i][2]<limit; i++){
                connect(edgeList[i][0],edgeList[i][1]);
            }
 
            return root(p)==root(q);
        }
    }

方法2：离线

我们也可以把所有结果提前算出来，放起来，需要的时候取出即可。每个边权都放一个并查集的parent. 这样就不用每次重置并查集了。

class DistanceLimitedPathsExist {
            int[] parent;
            int[] size;
            int n;
            int[][] edgeList;
            TreeMap<Integer,int[]> map;
        public DistanceLimitedPathsExist(int n, int[][] edgeList) {
            Arrays.sort(edgeList,(a,b)->a[2]-b[2]);
            parent = new int[n];
            size = new int[n];
            this.n = n;
            this.edgeList = edgeList;
            map = new TreeMap<>();
            for(int i = 0; i < n; i++){
                parent[i] = i;
                size[i] = 1;
            }
            map.put(0,Arrays.copyOf(parent,n));
            for(int [] edge:edgeList){
                int a = edge[0];
                int b = edge[1];
                int v = edge[2];
                connect(a,b);
                map.put(v,Arrays.copyOf(parent,n));
            }
 
        }
 
        private int root(int a){
            return parent[a]==a?a:root(parent[a]);
        }
 
        private void connect(int a, int b){
            int ra = root(a);
            int rb = root(b);
            if(ra==rb) return;
            if(size[ra]>size[rb]){
                size[ra]+=size[rb];
                parent[rb] = ra;
            }else{
                size[rb]+=size[ra];
                parent[ra] = rb;
            }
        }
 
 
        public boolean query(int p, int q, int limit) {
            this.parent = map.get(map.floorKey(limit-1));
            return root(p)==root(q);
        }
    }

方法3：快照

方法2是很不错，但是很占空间。如果并查集不优化，其实一次只会改变一个点。对同一版本进行较少次数修改，可以使用快照进行优化。

class DistanceLimitedPathsExist {
        SnapshotArray parent;
        public DistanceLimitedPathsExist(int n, int[][] edgeList) {
            Arrays.sort(edgeList,(a,b)->a[2]-b[2]);
            parent = new SnapshotArray(n);
            for(int i = 0; i < n; i++){
                parent.set(i,i,0);
            }
            for(int [] edge:edgeList){
                int a = edge[0];
                int b = edge[1];
                int v = edge[2];
                connect(a,b,v);
            }
 
        }
 
        private int root(int a,int v){
            return parent.get(a,v)==a?a:root(parent.get(a,v),v);
        }
 
        private void connect(int a, int b,int v){
            int ra = root(a,v);
            int rb = root(b,v);
            if(ra==rb) return;
            parent.set(rb,ra,v);
        }
 
 
        public boolean query(int p, int q, int limit) {
            return root(p,limit-1)==root(q,limit-1);
        }
 
        class SnapshotArray {
            Map<Integer,TreeMap<Integer,Integer>> indexVersion = new HashMap<>();
            int len = 0;
            public SnapshotArray(int length) {
                len = length;
            }
 
            public void set(int index, int val,int edition) {
                indexVersion.putIfAbsent(index,new TreeMap<>());
                indexVersion.get(index).put(edition,val);
            }
 
            public int get(int index, int snap_id) {
                TreeMap<Integer,Integer> map = indexVersion.getOrDefault(index,new TreeMap<>());
                return map.getOrDefault(map.floorKey(snap_id)==null?-1:map.floorKey(snap_id),0);
            }
        }
    }