Question

1724. 检查边长度限制的路径是否存在 II

English Version

题目描述

一张有 n 个节点的无向图以边的列表 edgeList 的形式定义，其中 edgeList[i] = [ui, vi, disi] 表示一条连接 ui 和 vi ，距离为 disi 的边。注意，同一对节点间可能有多条边，且该图可能不是连通的。

实现 DistanceLimitedPathsExist 类：

• DistanceLimitedPathsExist(int n, int[][] edgeList) 以给定的无向图初始化对象。
• boolean query(int p, int q, int limit) 当存在一条从 p 到 q 的路径，且路径中每条边的距离都严格小于 limit 时，返回 true ，否则返回 false 。

示例 1:

输入：
["DistanceLimitedPathsExist", "query", "query", "query", "query"]
[[6, [[0, 2, 4], [0, 3, 2], [1, 2, 3], [2, 3, 1], [4, 5, 5]]], [2, 3, 2], [1, 3, 3], [2, 0, 3], [0, 5, 6]]
输出：
[null, true, false, true, false]

解释：
DistanceLimitedPathsExist distanceLimitedPathsExist = new DistanceLimitedPathsExist(6, [[0, 2, 4], [0, 3, 2], [1, 2, 3], [2, 3, 1], [4, 5, 5]]);
distanceLimitedPathsExist.query(2, 3, 2); // 返回 true。存在一条从 2 到 3 ，距离为 1 的边，
                      // 这条边的距离小于 2。
distanceLimitedPathsExist.query(1, 3, 3); // 返回 false。从 1 到 3 之间不存在每条边的距离都
                      // 严格小于 3 的路径。
distanceLimitedPathsExist.query(2, 0, 3); // 返回 true。存在一条从 2 到 0 的路径，使得每条边的
                      // 距离 < 3：从 2 到 3 到 0 行进即可。
distanceLimitedPathsExist.query(0, 5, 6); // 返回 false。从 0 到 5 之间不存在路径。

提示：

• 2 <= n <= 104
• 0 <= edgeList.length <= 104
• edgeList[i].length == 3
• 0 <= ui, vi, p, q <= n-1
• ui != vi
• p != q
• 1 <= disi, limit <= 109
• 最多调用 104 次 query 。

解法

方法一：可持久化并查集

class PersistentUnionFind:
  def __init__(self, n):
    self.rank = [0] * n
    self.p = list(range(n))
    self.version = [inf] * n

  def find(self, x, t=inf):
    if self.p[x] == x or self.version[x] >= t:
      return x
    return self.find(self.p[x], t)

  def union(self, a, b, t):
    pa, pb = self.find(a), self.find(b)
    if pa == pb:
      return False
    if self.rank[pa] > self.rank[pb]:
      self.version[pb] = t
      self.p[pb] = pa
    else:
      self.version[pa] = t
      self.p[pa] = pb
      if self.rank[pa] == self.rank[pb]:
        self.rank[pb] += 1
    return True


class DistanceLimitedPathsExist:
  def __init__(self, n: int, edgeList: List[List[int]]):
    self.puf = PersistentUnionFind(n)
    edgeList.sort(key=lambda x: x[2])
    for u, v, dis in edgeList:
      self.puf.union(u, v, dis)

  def query(self, p: int, q: int, limit: int) -> bool:
    return self.puf.find(p, limit) == self.puf.find(q, limit)

class PersistentUnionFind {
  private final int inf = 1 << 30;
  private int[] rank;
  private int[] parent;
  private int[] version;

  public PersistentUnionFind(int n) {
    rank = new int[n];
    parent = new int[n];
    version = new int[n];
    for (int i = 0; i < n; i++) {
      parent[i] = i;
      version[i] = inf;
    }
  }

  public int find(int x, int t) {
    if (parent[x] == x || version[x] >= t) {
      return x;
    }
    return find(parent[x], t);
  }

  public boolean union(int a, int b, int t) {
    int pa = find(a, inf);
    int pb = find(b, inf);
    if (pa == pb) {
      return false;
    }
    if (rank[pa] > rank[pb]) {
      version[pb] = t;
      parent[pb] = pa;
    } else {
      version[pa] = t;
      parent[pa] = pb;
      if (rank[pa] == rank[pb]) {
        rank[pb]++;
      }
    }
    return true;
  }
}

public class DistanceLimitedPathsExist {
  private PersistentUnionFind puf;

  public DistanceLimitedPathsExist(int n, int[][] edgeList) {
    puf = new PersistentUnionFind(n);
    Arrays.sort(edgeList, (a, b) -> a[2] - b[2]);
    for (var e : edgeList) {
      puf.union(e[0], e[1], e[2]);
    }
  }

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

/**
 * Your DistanceLimitedPathsExist object will be instantiated and called as such:
 * DistanceLimitedPathsExist obj = new DistanceLimitedPathsExist(n, edgeList);
 * boolean param_1 = obj.query(p,q,limit);
 */

class PersistentUnionFind {
private:
  vector<int> rank;
  vector<int> parent;
  vector<int> version;

public:
  PersistentUnionFind(int n)
    : rank(n, 0)
    , parent(n)
    , version(n, INT_MAX) {
    for (int i = 0; i < n; i++) {
      parent[i] = i;
    }
  }

  int find(int x, int t) {
    if (parent[x] == x || version[x] >= t) {
      return x;
    }
    return find(parent[x], t);
  }

  bool unionSet(int a, int b, int t) {
    int pa = find(a, INT_MAX);
    int pb = find(b, INT_MAX);
    if (pa == pb) {
      return false;
    }
    if (rank[pa] > rank[pb]) {
      version[pb] = t;
      parent[pb] = pa;
    } else {
      version[pa] = t;
      parent[pa] = pb;
      if (rank[pa] == rank[pb]) {
        rank[pb]++;
      }
    }
    return true;
  }
};

class DistanceLimitedPathsExist {
private:
  PersistentUnionFind puf;

public:
  DistanceLimitedPathsExist(int n, vector<vector<int>>& edgeList)
    : puf(n) {
    sort(edgeList.begin(), edgeList.end(),
      [](const vector<int>& a, const vector<int>& b) {
        return a[2] < b[2];
      });

    for (const auto& edge : edgeList) {
      puf.unionSet(edge[0], edge[1], edge[2]);
    }
  }

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

/**
 * Your DistanceLimitedPathsExist object will be instantiated and called as such:
 * DistanceLimitedPathsExist* obj = new DistanceLimitedPathsExist(n, edgeList);
 * bool param_1 = obj->query(p,q,limit);
 */

type PersistentUnionFind struct {
  rank  []int
  parent  []int
  version []int
}

func NewPersistentUnionFind(n int) *PersistentUnionFind {
  rank := make([]int, n)
  parent := make([]int, n)
  version := make([]int, n)

  for i := 0; i < n; i++ {
    parent[i] = i
  }

  return &PersistentUnionFind{
    rank:  rank,
    parent:  parent,
    version: version,
  }
}

func (uf *PersistentUnionFind) find(x int, t int) int {
  if uf.parent[x] == x || uf.version[x] >= t {
    return x
  }
  return uf.find(uf.parent[x], t)
}

func (uf *PersistentUnionFind) union(a, b, t int) bool {
  pa := uf.find(a, int(^uint(0)>>1))
  pb := uf.find(b, int(^uint(0)>>1))

  if pa == pb {
    return false
  }

  if uf.rank[pa] > uf.rank[pb] {
    uf.version[pb] = t
    uf.parent[pb] = pa
  } else {
    uf.version[pa] = t
    uf.parent[pa] = pb
    if uf.rank[pa] == uf.rank[pb] {
      uf.rank[pb]++
    }
  }

  return true
}

type DistanceLimitedPathsExist struct {
  puf *PersistentUnionFind
}

func Constructor(n int, edgeList [][]int) DistanceLimitedPathsExist {
  sort.Slice(edgeList, func(i, j int) bool {
    return edgeList[i][2] < edgeList[j][2]
  })

  puf := NewPersistentUnionFind(n)

  for _, edge := range edgeList {
    puf.union(edge[0], edge[1], edge[2])
  }

  return DistanceLimitedPathsExist{
    puf: puf,
  }
}

func (dle *DistanceLimitedPathsExist) Query(p, q, limit int) bool {
  return dle.puf.find(p, limit) == dle.puf.find(q, limit)
}

/**
 * Your DistanceLimitedPathsExist object will be instantiated and called as such:
 * obj := Constructor(n, edgeList);
 * param_1 := obj.Query(p,q,limit);
 */

class PersistentUnionFind {
  private rank: number[];
  private parent: number[];
  private version: number[];

  constructor(n: number) {
    this.rank = Array(n).fill(0);
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.version = Array(n).fill(Infinity);
  }

  find(x: number, t: number): number {
    if (this.parent[x] === x || this.version[x] >= t) {
      return x;
    }
    return this.find(this.parent[x], t);
  }

  union(a: number, b: number, t: number): boolean {
    const pa = this.find(a, Infinity);
    const pb = this.find(b, Infinity);

    if (pa === pb) {
      return false;
    }

    if (this.rank[pa] > this.rank[pb]) {
      this.version[pb] = t;
      this.parent[pb] = pa;
    } else {
      this.version[pa] = t;
      this.parent[pa] = pb;
      if (this.rank[pa] === this.rank[pb]) {
        this.rank[pb]++;
      }
    }

    return true;
  }
}

class DistanceLimitedPathsExist {
  private puf: PersistentUnionFind;

  constructor(n: number, edgeList: number[][]) {
    this.puf = new PersistentUnionFind(n);
    edgeList.sort((a, b) => a[2] - b[2]);
    for (const [u, v, dis] of edgeList) {
      this.puf.union(u, v, dis);
    }
  }

  query(p: number, q: number, limit: number): boolean {
    return this.puf.find(p, limit) === this.puf.find(q, limit);
  }
}

/**
 * Your DistanceLimitedPathsExist object will be instantiated and called as such:
 * var obj = new DistanceLimitedPathsExist(n, edgeList)
 * var param_1 = obj.query(p,q,limit)
 */