Hard

题目描述

一个有 n 个节点的无向图由 edgeList 定义，其中 edgeList[i] = [ui, vi, disi] 表示节点 ui 和 vi 之间有一条距离为 disi 的边。注意，两个节点之间可能存在多条边。

给定一个查询数组 queries，其中 queries[j] = [pj, qj, limitj]，你的任务是判断对于每个查询 queries[j]，是否存在一条从 pj 到 qj 的路径，使得路径上的每条边的距离都严格小于 limitj。

返回一个布尔数组 answer，其中 answer.length == queries.length，answer 的第 j 个值为 true 当且仅当 queries[j] 存在满足条件的路径，否则为 false。

示例 1：

输入：n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
输出：[false,true]
解释：上图显示了给定的图。注意在节点 0 和 1 之间有两条重叠的边，距离分别为 2 和 16。
对于第一个查询，在 0 和 1 之间没有路径使得每条边的距离都小于 2，因此返回 false。
对于第二个查询，存在一条路径 (0 -> 1 -> 2)，两条边的距离都小于 5，因此返回 true。

示例 2：

输入：n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
输出：[true,false]

约束条件：

  • 2 <= n <= 10^5
  • 1 <= edgeList.length, queries.length <= 10^5
  • edgeList[i].length == 3
  • queries[j].length == 3
  • 0 <= ui, vi, pj, qj <= n - 1
  • ui != vi
  • pj != qj
  • 1 <= disi, limitj <= 10^9
  • 两个节点之间可能存在多条边

解题思路

这道题的关键在于理解题意：我们需要判断在给定限制条件下，两点之间是否存在连通路径。

思路分析：

最直观的想法是对每个查询单独处理，但这样会导致大量重复计算。题目提示告诉我们可以重新排序查询来避免重复计算，这提示我们使用离线算法。

核心思想是将查询按限制值排序，边按权重排序，然后使用并查集动态维护连通性：

  1. 预处理：将所有查询按 limit 值升序排序，同时记录原始索引
  2. 排序边：将所有边按权重升序排序
  3. 离线处理：
    • 使用并查集维护当前可用边构成的连通图
    • 对于每个查询（按 limit 排序后的顺序）：
      • 将所有权重小于当前 limit 的边加入并查集
      • 查询两点是否在同一连通分量中

这种方法的优势在于：

  • 每条边最多被加入并查集一次
  • 查询之间可以复用之前建立的连通关系
  • 时间复杂度优化到 O((E+Q)log(E+Q) + (E+Q)α(N))

算法步骤：

  1. 为查询添加索引并按 limit 排序
  2. 按边权重排序
  3. 使用双指针技术，边处理查询边动态添加边到并查集
  4. 将结果按原始查询顺序输出

代码实现

class Solution {
public:
    vector<int> parent;
    
    int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    
    void unite(int x, int y) {
        int px = find(x), py = find(y);
        if (px != py) {
            parent[px] = py;
        }
    }
    
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        parent.resize(n);
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // 为查询添加索引
        vector<vector<int>> indexedQueries;
        for (int i = 0; i < queries.size(); i++) {
            indexedQueries.push_back({queries[i][0], queries[i][1], queries[i][2], i});
        }
        
        // 按限制值排序查询
        sort(indexedQueries.begin(), indexedQueries.end(), 
             [](const vector<int>& a, const vector<int>& b) {
                 return a[2] < b[2];
             });
        
        // 按权重排序边
        sort(edgeList.begin(), edgeList.end(), 
             [](const vector<int>& a, const vector<int>& b) {
                 return a[2] < b[2];
             });
        
        vector<bool> result(queries.size());
        int edgeIndex = 0;
        
        for (const auto& query : indexedQueries) {
            int p = query[0], q = query[1], limit = query[2], originalIndex = query[3];
            
            // 添加所有权重小于limit的边
            while (edgeIndex < edgeList.size() && edgeList[edgeIndex][2] < limit) {
                unite(edgeList[edgeIndex][0], edgeList[edgeIndex][1]);
                edgeIndex++;
            }
            
            // 检查连通性
            result[originalIndex] = (find(p) == find(q));
        }
        
        return result;
    }
};

class Solution:
    def distanceLimitedPathsExist(self, n: int, edgeList: List[List[int]], queries: List[List[int]]) -> List[bool]:
        # 并查集
        parent = list(range(n))
        
        def find(x):
            if parent[x] != x:
                parent[x] = find(parent[x])
            return parent[x]
        
        def unite(x, y):
            px, py = find(x), find(y)
            if px != py:
                parent[px] = py
        
        # 为查询添加索引并按limit排序
        indexed_queries = []
        for i, (p, q, limit) in enumerate(queries):
            indexed_queries.append((p, q, limit, i))
        indexed_queries.sort(key=lambda x: x[2])
        
        # 按权重排序边
        edgeList.sort(key=lambda x: x[2])
        
        result = [False] * len(queries)
        edge_index = 0
        
        for p, q, limit, original_index in indexed_queries:
            # 添加所有权重小于limit的边
            while edge_index < len(edgeList) and edgeList[edge_index][2] < limit:
                unite(edgeList[edge_index][0], edgeList[edge_index][1])
                edge_index += 1
            
            # 检查连通性
            result[original_index] = (find(p) == find(q))
        
        return result

public class Solution {
    private int[] parent;
    
    private int Find(int x) {
        if (parent[x] != x) {
            parent[x] = Find(parent[x]);
        }
        return parent[x];
    }
    
    private void Unite(int x, int y) {
        int px = Find(x), py = Find(y);
        if (px != py) {
            parent[px] = py;
        }
    }
    
    public bool[] DistanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        parent = new int[n];
        for (int i = 0; i < n; i++) {
            parent[i] = i;
        }
        
        // 为查询添加索引
        var indexedQueries = new List<(int p, int q, int limit, int index)>();
        for (int i = 0; i < queries.Length; i++) {
            indexedQueries.Add((queries[i][0], queries[i][1], queries[i][2], i));
        }
        
        // 按限制值排序查询
        indexedQueries.Sort((a, b) => a.limit.CompareTo(b.limit));
        
        // 按权重排序边
        Array.Sort(edgeList, (a, b) => a[2].CompareTo(b[2]));
        
        bool[] result = new bool[queries.Length];
        int edgeIndex = 0;
        
        foreach (var query in indexedQueries) {
            // 添加所有权重小于limit的边
            while (edgeIndex < edgeList.Length && edgeList[edgeIndex][2] < query.limit) {
                Unite(edgeList[edgeIndex][0], edgeList[edgeIndex][1]);
                edgeIndex++;
            }
            
            // 检查连通性
            result[query.index] = (Find(query.p) == Find(query.q));
        }
        
        return result;
    }
}

var distanceLimitedPathsExist = function(n, edgeList, queries) {
    class UnionFind {
        constructor(n) {
            this.parent = Array.from({length: n}, (_, i) => i);
            this.rank = new Array(n).fill(0);
        }
        
        find(x) {
            if (this.parent[x] !== x) {
                this.parent[x] = this.find(this.parent[x]);
            }
            return this.parent[x];
        }
        
        union(x, y) {
            const rootX = this.find(x);
            const rootY = this.find(y);
            
            if (rootX !== rootY) {
                if (this.rank[rootX] < this.rank[rootY]) {
                    this.parent[rootX] = rootY;
                } else if (this.rank[rootX] > this.rank[rootY]) {
                    this.parent[rootY] = rootX;
                } else {
                    this.parent[rootY] = rootX;
                    this.rank[rootX]++;
                }
            }
        }
        
        connected(x, y) {
            return this.find(x) === this.find(y);
        }
    }
    
    edgeList.sort((a, b) => a[2] - b[2]);
    
    const queryIndices = queries.map((query, i) => [query[0], query[1], query[2], i]);
    queryIndices.sort((a, b) => a[2] - b[2]);
    
    const result = new Array(queries.length);
    const uf = new UnionFind(n);
    let edgeIndex = 0;
    
    for (const [p, q, limit, originalIndex] of queryIndices) {
        while (edgeIndex < edgeList.length && edgeList[edgeIndex][2] < limit) {
            const [u, v] = edgeList[edgeIndex];
            uf.union(u, v);
            edgeIndex++;
        }
        
        result[originalIndex] = uf.connected(p, q);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

操作时间复杂度空间复杂度
排序查询O(Q log Q)O(Q)
排序边O(E log E)O(1)
并查集操作O((E+Q)α(N))O(N)
总体O((E+Q)log(E+Q))O(N+Q)

其中 N 是节点数，E 是边数，Q 是查询数，α 是阿克曼函数的反函数（实际中可视为常数）。

相关题目