{"id":7830,"date":"2020-12-20T02:00:20","date_gmt":"2020-12-20T10:00:20","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=7830"},"modified":"2020-12-22T22:34:03","modified_gmt":"2020-12-23T06:34:03","slug":"leetcode-1697-checking-existence-of-edge-length-limited-paths","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/graph\/leetcode-1697-checking-existence-of-edge-length-limited-paths\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 1697. Checking Existence of Edge Length Limited Paths"},"content":{"rendered":"\n

An undirected graph of n<\/code> nodes is defined by edgeList<\/code>, where edgeList[i] = [ui<\/sub>, vi<\/sub>, disi<\/sub>]<\/code> denotes an edge between nodes ui<\/sub><\/code> and vi<\/sub><\/code> with distance disi<\/sub><\/code>. Note that there may be multiple<\/strong> edges between two nodes.<\/p>\n\n\n\n

Given an array queries<\/code>, where queries[j] = [pj<\/sub>, qj<\/sub>, limitj<\/sub>]<\/code>, your task is to determine for each queries[j]<\/code> whether there is a path between pj<\/sub><\/code> and qj<\/sub><\/code>such that each edge on the path has a distance strictly less than<\/strong> limitj<\/sub><\/code> .<\/p>\n\n\n\n

Return a boolean array<\/strong> <\/em>answer<\/code>, where <\/em>answer.length == queries.length<\/code> and the <\/em>jth<\/sup><\/code> value of <\/em>answer<\/code> is <\/em>true<\/code> if there is a path for <\/em>queries[j]<\/code> is <\/em>true<\/code>, and <\/em>false<\/code> otherwise<\/em>.<\/p>\n\n\n\n

Example 1:<\/strong><\/p>\n\n\n\n

\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]\nOutput:<\/strong> [false,true]\nExplanation:<\/strong> The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.\nFor the first query, between 0 and 1 there is no path where each distance is less than 2, thus we return false for this query.\nFor the second query, there is a path (0 -> 1 -> 2) of two edges with distances less than 5, thus we return true for this query.\n<\/pre>\n\n\n\n
Example 2:<\/strong><\/p>\n\n\n\n
\"\"\/<\/figure>\n\n\n\n
Input:<\/strong> n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]\nOutput:<\/strong> [true,false]\nExaplanation:<\/strong> The above figure shows the given graph.\n<\/pre>\n\n\n\n
Constraints:<\/strong><\/p>\n\n\n\n
  • 2 <= n <= 105<\/sup><\/code><\/li>
  • 1 <= edgeList.length, queries.length <= 105<\/sup><\/code><\/li>
  • edgeList[i].length == 3<\/code><\/li>
  • queries[j].length == 3<\/code><\/li>
  • 0 <= ui<\/sub>, vi<\/sub>, pj<\/sub>, qj<\/sub> <= n - 1<\/code><\/li>
  • ui<\/sub> != vi<\/sub><\/code><\/li>
  • pj<\/sub> != qj<\/sub><\/code><\/li>
  • 1 <= disi<\/sub>, limitj<\/sub> <= 109<\/sup><\/code><\/li>
  • There may be multiple<\/strong> edges between two nodes.<\/li><\/ul>\n\n\n\n
    Solution: Union Find<\/strong><\/h2>\n\n\n\n
    Since queries are offline, we can reorder them to optimize time complexity. Answer queries by their limits in ascending order while union edges by weights up to the limit. In this case, we just need to go through the entire edge list at most once.<\/p>\n\n\n\n
    Time complexity: O(QlogQ + ElogE)
    Space complexity: O(Q + E)<\/p>\n\n\n\n
    \n
    C++<\/h2>\n
    \n\n
    \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector distanceLimitedPathsExist(int n, vector>& E, vector>& Q) {\n    vector parents(n);\n    iota(begin(parents), end(parents), 0);\n    function find = [&](int x) {\n      return parents[x] == x ? x : parents[x] = find(parents[x]);\n    };\n    const int m = Q.size();\n    for (int i = 0; i < m; ++i) Q[i].push_back(i);\n    \/\/ Sort edges by weight in ascending order.\n    sort(begin(E), end(E), [](const auto& a, const auto& b) { return a[2] < b[2]; });\n    \/\/ Sort queries by limit in ascending order\n    sort(begin(Q), end(Q), [](const auto& a, const auto& b) { return a[2] < b[2]; });\n    vector ans(m);\n    int i = 0;\n    for (const auto& q : Q) {      \n      while (i < E.size() && E[i][2] < q[2])\n        parents[find(E[i++][0])] = find(E[i][1]);        \n      ans[q[3]] = find(q[0]) == find(q[1]);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
    <\/p>\n","protected":false},"excerpt":{"rendered":"
    An undirected graph of n nodes is defined by edgeList, where edgeList[i] = [ui, vi, disi] denotes an edge between nodes ui and vi with distance disi. Note that there may be multiple edges between two nodes.…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[76],"tags":[77,217,15,113],"class_list":["post-7830","post","type-post","status-publish","format-standard","hentry","category-graph","tag-graph","tag-hard","tag-sorting","tag-union-find","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7830","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=7830"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7830\/revisions"}],"predecessor-version":[{"id":7839,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/7830\/revisions\/7839"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=7830"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=7830"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=7830"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}