2023-04-29 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's April LeetCoding Challenge with cpp.

April LeetCoding Challenge 29

Description

Checking Existence of Edge Length Limited Paths

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.

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

Return a boolean array answer, where answer.length == queries.length and the jth value of answer is true if there is a path for queries[j] is true, and false otherwise.

 

Example 1:

Input: n = 3, edgeList = [[0,1,2],[1,2,4],[2,0,8],[1,0,16]], queries = [[0,1,2],[0,2,5]]
Output: [false,true]
Explanation: The above figure shows the given graph. Note that there are two overlapping edges between 0 and 1 with distances 2 and 16.
For 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.
For 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.

Example 2:

Input: n = 5, edgeList = [[0,1,10],[1,2,5],[2,3,9],[3,4,13]], queries = [[0,4,14],[1,4,13]]
Output: [true,false]
Exaplanation: The above figure shows the given graph.

 

Constraints:

  • 2 <= n <= 105
  • 1 <= edgeList.length, queries.length <= 105
  • edgeList[i].length == 3
  • queries[j].length == 3
  • 0 <= ui, vi, pj, qj <= n - 1
  • ui != vi
  • pj != qj
  • 1 <= disi, limitj <= 109
  • There may be multiple edges between two nodes.

Solution

auto speedup = [](){
  cin.tie(nullptr);
  cout.tie(nullptr);
  ios::sync_with_stdio(false);
  return 0;
}();
class Solution {
  vector<int> parent;
  int curIndex;
  void init(int n, vector<vector<int>>& edgeList) {
    curIndex = 0;
    sort(edgeList.begin(), edgeList.end(), [](const vector<int>& a, const vector<int>& b) {
      return a[2] < b[2];
    });
    parent.resize(n);
    for(int i = 0; i < n; ++i) {
      parent[i] = i;
    }
  }
  
  int find(int x) {
    if(parent[x] != x) parent[x] = find(parent[x]);
    return parent[x];
  }

  void merge(int x, int y) {
    int px = find(x);
    int py = find(y);
    parent[px] = py;
  }

  void solveToLength(int len, vector<vector<int>>& edgeList) {
    for(; curIndex < edgeList.size() && edgeList[curIndex][2] < len; ++curIndex) {
      merge(edgeList[curIndex][1], edgeList[curIndex][0]);
    }
  }
public:
  vector<bool> distanceLimitedPathsExist(int n, vector<vector<int>>& edgeList, vector<vector<int>>& queries) {
    init(n, edgeList);
    int len = queries.size();
    vector<int> order(len);
    vector<bool> answer(len);
    for(int i = 0; i < len; ++i) {
      order[i] = i;
    }
    sort(order.begin(), order.end(), [&](int a, int b) {
      return queries[a][2] < queries[b][2];
    });
    for(auto i : order) {
      solveToLength(queries[i][2], edgeList);
      answer[i] = (find(queries[i][0]) == find(queries[i][1]));
    }
    return answer;
  }
};

// Accepted
// 23/23 cases passed (476 ms)
// Your runtime beats 98.73 % of cpp submissions
// Your memory usage beats 84.81 % of cpp submissions (109.6 MB)
Algorithm