C++ Union Find
Solution 1. Union Find\n\nSort the edges from small distance to large distance.\n\nTraverse the queries from small limit to large limit. Given a limit, we union
## Solution 1. Union Find\n\nSort the edges from small distance to large distance.\n\nTraverse the queries from small limit to large limit. Given a limit, we union the nodes that can be connected. \n\nIn this way, we just need to traverse the edges that are smaller than the limit. Since we are visiting the queries with increasing limit, we just need to visit the edges once from small distance to large distance.\n\n```cpp\n// OJ: https://leetcode.com/contest/weekly-contest-220/problems/checking-existence-of-edge-length-limited-paths/\n// Author: github.com/lzl124631x\n// Time: O(ElogE + QlogQ)\n// Space: O(N)\nclass UnionFind {\n    vector<int> id;\npublic:\n    UnionFind(int n) : id(n) {\n        iota(begin(id), end(id), 0);\n    }\n    void connect(int a, int b) {\n        int x = find(a), y = find(b);\n        if (x == y) return;\n        id[x] = y;\n    }\n    bool connected(int i, int j) { return find(i) == find(j); }\n    int find(int a) {\n        return id[a] == a ? a : (id[a] = find(id[a]));\n    }\n};\nclass Solution {\npublic:\n    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& E, vector<vector<int>>& Q) {\n        vector<bool> ans(Q.size());\n        for (int i = 0; i < Q.size(); ++i) Q[i].push_back(i);\n        sort(begin(Q), end(Q), [&](auto &a, auto &b) { return a[2] < b[2]; });\n        sort(begin(E), end(E), [&](auto &a, auto &b) { return a[2] < b[2]; });\n        UnionFind uf(n);\n        int i = 0;\n        for (auto &q : Q) { // traverse the queries from small limit to large limit\n            int u = q[0], v = q[1], limit = q[2], qid = q[3];\n            for (; i < E.size() && E[i][2] < limit; ++i) uf.connect(E[i][0], E[i][1]); // visit the edges that are smaller than the limit\n            ans[qid] = uf.connected(u, v);\n        }\n        return ans;\n    }\n};\n```
[]