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

[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