1697. 檢查邊長度限制的路徑是否存在

思路

與其每次查詢都跑一遍 bfs/dfs，不如將查詢的順序調動。
對查詢跟邊排序，排序時依據dist跟limit。
此時每次查詢的限制條件，只會越來越放寬，
這樣對於後面的查詢來說，此時要處理limit為 10 的查詢時，先將所有長度 < 10 的邊都合併，
然後直接查詢兩點是否連通就好，使用並查集來合併節點。

程式碼

並查集

class Solution {
private:
    static const int MX = 1e5+1;
    int parent[MX];
    void build(int n) {
        iota(parent, parent + n, 0);
    }
    int find(int x) {
        if(x != parent[x]) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    bool isSameSet(int x, int y) {
        return find(x) == find(y);
    }
    void unite(int x, int y) {
        parent[find(x)] = parent[find(y)];
    }
public:
    vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
        build(n);
        for(int i = 0; i < queries.size(); i++) {
            queries[i].push_back(i); // 後面排序會打亂順序，事先加入下標，以供填入答案
        }
        sort(queries.begin(), queries.end(), [&](vector<int>& a, vector<int>& b) {
            return a[2] < b[2];
        });
        sort(edgeList.begin(), edgeList.end(), [&](vector<int>& a, vector<int>& b) {
            return a[2] < b[2];
        });
        vector<bool> res(queries.size());
        int m = edgeList.size();
        int i = 0;
        for(auto& vec : queries) {
            int p = vec[0], q = vec[1], limit = vec[2];
            while(i < m && edgeList[i][2] < limit) {
                unite(edgeList[i][0], edgeList[i][1]);
                i++;
            }
            if(isSameSet(p, q)) res[vec[3]] = true;
            else res[vec[3]] = false;
        }
        return res;      
    }
};

複雜度分析

• 時間複雜度：$O(E\log{E}+Q\log{Q}+Q\alpha(n))$，$E$ 是邊的個數，$Q$ 是查詢次數
• 空間複雜度：$O(N+Q)$