Union Find and two-pointer

This is the fourth problem of the weekly contest of Leetcode Dec 19, 2020.

1697. Checking Existence of Edge Length Limited Paths

time complexity

O(E log E + Q log Q)

The basis idea is building the graph gradually with the following constrains:

The maximum edge should be less than the limit.

In order to do this, we should sort the edge and querries firstly and then using two pointers to control the whole process. This is a pretty nice practice for both the Union Find algorithm and Two Pointers.

Reference

[1]https://leetcode.com/problems/checking-existence-of-edge-length-limited-paths/discuss/978449/C%2B%2B-solution-with-disjoint-set-%2B-two-pointers-~O(nlogn)

[2] https://youtu.be/d-HJMOdEM7I