写在前面
又是一道周赛第四题，这周起晚了，写了两题后边就没时间想了，这道第四题还是挺有意思的，之前也没有遇到过这种类型的离线化思想，特此记录一下。
题目
核心思路
图论的问题，题目还给出了所有边，很容易想到使用并查集+边排序进行解答，对于任一个目标查询[p, q, limit]，如果所有长度小于limit的边加入到图中可以使得p 和 q 连通，即代表该查询可以得到true的结果。
不过，如果直接对每个查询结果均要如此操作，其复杂度将接近O(n ^ 2)，对于题目给出的复杂度显然是解决不了的，于是就要考虑优化的思路了。
离线化
在提出优化思路之前，先给出离线化的概念。
所谓的离线化，就是事先给出了所有可能的查询，然后解决问题时就可以不按照给出的顺序进行解答，从而避免重复计算，达到优化时间复杂度的效果。
优化思路
根据上述核心思路，优先处理limit小的查询必然不会产生重复的计算，所以将题目给出的queries数组按照第三个属性limit进行从小到大的排序，就可以优化时间复杂度。不过这里还有需要一个小技巧，因为虽然我们将queries排序了，但是还是需要知道排序后的原始下标以存储最终答案，所以这里可以使用一个辅助数组idxs来存储每个查询query的下标，然后根据题目给出的数组queries对idxs进行排序即可，排序方式如下：
//排序查询
Integer[] idxs = new Integer[len];
for(int i = 0; i < len; i++) idxs[i] = i;
Arrays.sort(idxs, (i1, i2) -> queries[i1][2] - queries[i2][2]);
这样通过比较器排序，就可以保证idxs下标遍历时，对应的limit值递增。
完整代码
class Solution {
int[] p;//并查集
int find(int x){
if(x != p[x]) p[x] = find(p[x]);
return p[x];
}
public boolean[] distanceLimitedPathsExist(int n, int[][] edgeList, int[][] queries) {
int len = queries.length;
boolean[] res = new boolean[len];
p = new int[n];
//初始化并查集
for(int i = 0; i < n; i++) p[i] = i;
//排序边集
Arrays.sort(edgeList, (e1, e2) -> e1[2] - e2[2]);
//排序查询
Integer[] idxs = new Integer[len];
for(int i = 0; i < len; i++) idxs[i] = i;
Arrays.sort(idxs, (i1, i2) -> queries[i1][2] - queries[i2][2]);
int i = 0;
for(int idx : idxs){
int[] query = queries[idx];
while(i < edgeList.length && edgeList[i][2] < query[2]){
int x = edgeList[i][0], y = edgeList[i][1];
int px = find(x), py = find(y);
if(px != py){
p[px] = py;
}
i++;
}
res[idx] = find(query[0]) == find(query[1]);
}
return res;
}
}
虽然做过很多道题目都给了所有可能的查询条件，但是实际上，需要根据需求调整顺序这还是头一回，这种离线化的思想对于优化时间复杂度可以有很大的帮助，另外，保存下标的排序小技巧也是个不错的小知识点。
文章如果有写的不正确的地方还请指出，感恩相遇~~~
