https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/
谁能想到是并查集呀！
想不到想不到，记录下来！

个人解答

  1. class Solution:
  2.     def distanceLimitedPathsExist(self, n: int, es: List[List[int]], qs: List[List[int]]) -> List[bool]:
  3.         qs = sorted([[p, q, l, i] for i, (p, q, l) in enumerate(qs)], key=lambda x:x[2])
  4.         es.sort(key=lambda x:x[2])
  5.         st = [-1] * n
  7.         def setFind(st, x):
  8.             if st[x] < 0:
  9.                 return x
  10.             st[x] = setFind(st, st[x])
  11.             return st[x]
  13.         def setUnion(st, x, y):
  14.             rx = setFind(st, x)
  15.             ry = setFind(st, y)
  16.             if rx == ry:
  17.                 return
  18.             if st[rx] < st[ry]:
  19.                 st[rx] += st[ry]
  20.                 st[ry] = rx
  21.             else:
  22.                 st[ry] += st[rx]
  23.                 st[rx] = ry
  25.         ei = 0
  26.         res = [False] * len(qs)
  27.         for p, q, l, i in qs:
  28.             while ei < len(es) and es[ei][2] < l:
  29.                 u, v, _ = es[ei]
  30.                 setUnion(st, u, v)
  31.                 ei += 1
  32.             res[i] = setFind(st, p) == setFind(st, q)
  33.         return res

题目分析

参考：https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/discuss/978450/C%2B%2B-DSU-%2B-Two-Pointers

一眼看过去，是关于图的问题，求all-pair shortest path的问题。可是，限制条件可是10^5，来一个N^2的算法估计都超时了。

这道题，由于queries是事先给的，而最终，也只是要这些queries对应的结果。
对queries按照limit排序，那么后边的大的limit的query，或许可以利用前边的状态。
对于一个limit，计算出在该limit下，所有点能相互连接的状态。由于边也是可以sort的，所以这个也只用扫一遍就可以确定。
而能够记录点的相互连接状态，就是经典的并查集的应用了。

将queries和edges对limit/length进行sort之后
对于每一个query，将小于当前limit的点都join起来，判断能否连接直接判断是不是在一个set中即可
set的关系，对于更大的limit也是适用的，所以不断累积就可以了
妙！