Skip to content

1724. Checking Existence of Edge Length Limited Paths II 👍

  • Time:
    • Constructor: $O(|V| + |E|\log |E|)$
    • query(p: int, q: int, limit: int): $O(|\log^2 |V|)$
  • Space: $O(|V| + |E|)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
class UnionFind {
 public:
  UnionFind() {}
  UnionFind(int n) {
    id.resize(n);

    for (int i = 0; i < n; ++i)
      id[i][0] = i;
  }

  void union_(int u, int v, int limit) {
    const int i = find(u, limit);
    const int j = find(v, limit);
    if (i == j)
      return;
    id[i][limit] = j;
  }

  int find(int u, int limit) {
    // the minimum iterator of id[u] > limit
    const auto it = id[u].upper_bound(limit);
    const int i = prev(it)->second;
    if (i == u)
      return u;
    // Recursively find i's id.
    const int j = find(i, limit);
    id[u][limit] = j;
    return j;
  }

 private:
  // id[i]'s (key, value) := (limit, id of node i <= limit)
  vector<map<int, int>> id;
};

class DistanceLimitedPathsExist {
 public:
  DistanceLimitedPathsExist(int n, vector<vector<int>>& edgeList) {
    uf = UnionFind(n);

    ranges::sort(edgeList, ranges::less{},
                 [](const vector<int>& edge) { return edge[2]; });

    for (const vector<int>& edge : edgeList) {
      const int u = edge[0];
      const int v = edge[1];
      const int d = edge[2];
      uf.union_(u, v, d);
    }
  }

  bool query(int p, int q, int limit) {
    return uf.find(p, limit - 1) == uf.find(q, limit - 1);
  }

 private:
  UnionFind uf;
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class UnionFind {
  public UnionFind(int n) {
    id = new TreeMap[n];
    for (int i = 0; i < n; ++i) {
      id[i] = new TreeMap<>();
      id[i].put(0, i);
    }
  }

  public void union(int u, int v, int limit) {
    final int i = find(u, limit);
    final int j = find(v, limit);
    if (i == j)
      return;
    id[i].put(limit, j);
  }

  public int find(int u, int limit) {
    // the maximum key of id[u] <= limit
    final int floorKey = id[u].floorKey(limit);
    final int i = id[u].get(floorKey);
    if (i == u)
      return u;
    // Recursively find i's id.
    final int j = find(i, limit);
    id[u].put(limit, j);
    return j;
  }

  // id[i]'s (key, value) := (limit, id of node i <= limit)
  private TreeMap<Integer, Integer>[] id;
}

class DistanceLimitedPathsExist {
  public DistanceLimitedPathsExist(int n, int[][] edgeList) {
    uf = new UnionFind(n);

    Arrays.sort(edgeList, (a, b) -> Integer.compare(a[2], b[2]));

    for (int[] edge : edgeList) {
      final int u = edge[0];
      final int v = edge[1];
      final int d = edge[2];
      uf.union(u, v, d);
    }
  }

  public boolean query(int p, int q, int limit) {
    return uf.find(p, limit - 1) == uf.find(q, limit - 1);
  }

  private UnionFind uf;
}