LC.P1697[检查边长度限制的路径是否存在]

方法一：离线查询+并查集

离线查询：对于一道题目会给出若干询问，而这些询问是全部提前给出的，也就是说，不必按照询问的顺序依次对它们进行处理，而是可以按照某种顺序（例如全序、偏序（拓扑序）、树的 DFS 序等）或者把所有询问看成一个整体（例如整体二分、莫队算法等）进行处理。

与「离线」相对应的是「在线」思维，即所有的询问是依次给出的，在返回第 $k$ 个询问的答案之前，不会获得第
$k+1$ 个询问。

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
class Solution {
    int[] p;

    private int find(int x) {
        if (p[x] != x) p[x] = find(p[x]);
        return p[x];
    }

    private void union(int a, int b) {
        p[find(a)] = p[find(b)];
    }

    public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
        p = new int[n];
        for (int i = 0; i < n; ++i) p[i] = i;
        Arrays.sort(edgeList, (a, b) -> a[2] - b[2]);
        int m = queries.length;
        Integer[] index = new Integer[m];
        for (int i = 0; i < m; ++i) index[i] = i;
        Arrays.sort(index, (a, b) -> queries[a][2] - queries[b][2]);
        boolean[] ans = new boolean[m];
        int j = 0;
        for (int i : index) {
            int a = queries[i][0], b = queries[i][1], limit = queries[i][2];
            while (j < edgeList.length && edgeList[j][2] < limit) {
                int u = edgeList[j][0], v = edgeList[j][1];
                union(u, v);
                ++j;
            }
            ans[i] = find(a) == find(b);
        }
        return ans;
    }
}