# Union Find and two-pointer

## 1697. Checking Existence of Edge Length Limited Paths

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.

`class UnionFind {    private:    vector<int> parent;    public:    UnionFind(int n) {        parent.assign(n, 0);        for (int i = 0; i < n; ++i) parent[i] = i;    }    int find(int x) {        return parent[x] = parent[x] == x ? x : find(parent[x]);    }    void unionSet(int x, int y) {        parent[find(y)] = find(x);      }    bool isSameSet(int x, int y) {        return find(x) == find(y);    }};class Solution {public:    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& e, vector<vector<int>>& queries) {        UnionFind uf(n);        vector<vector<int>> q;        for (int i = 0; i < (int)queries.size(); ++i) {            auto v = queries[i];            v.push_back(i);            q.push_back(v);        }        sort(q.begin(), q.end(),            [](const vector<int>& lhs, const vector<int>& rhs) {               return lhs[2] < rhs[2];             });        sort(e.begin(), e.end(),            [](const vector<int>& lhs, const vector<int>& rhs) {               return lhs[2] < rhs[2];             });        vector<bool> ret(q.size());        int j = 0;        for (int i = 0; i < (int)q.size(); ++i) {            while(j < e.size() && e[j][2] < q[i][2]) {                uf.unionSet(e[j][0], e[j][1]);                j++;            }            ret[q[i][3]] = uf.isSameSet(q[i][0], q[i][1]);        }        return ret;       }};`

# Reference

## More from Jimmy Shen

Data Scientist/MLE/SWE @takemobi

Love podcasts or audiobooks? Learn on the go with our new app.