Demo önizleme: Bu çözümler otomatik test paketini geçiyor ama insan tarafından incelenmedi. Trade-off ve yazıları taslak olarak değerlendirin.

Checking Existence of Edge Length Limited Paths II

Problem (yeniden ifade)

DistanceLimitedPathsExist(n, edgeList) tasarla; query(p, q, limit): p → q yolunun maksimum kenarı limit’ten kesin küçükse true. Sorgular çevrimiçi.

Sezgi

İki köşe arasındaki min-max darboğaz, MST’deki tek yol üzerindedir. Kruskal o ağacı kurar; ikili kaldırma parent[k][v] ve maxEdge[k][v] ile 2^k sıçrama tutar. Sorgu: “yoldaki max < limit”. Kopuk → false.

Yaklaşımlar

MST + ikili kaldırma

Doğrulanmadı

Zaman O((n+E) log n) kurulum, O(log n) sorguAlan O(n log n)

Fikir. Kenarları sırala, Kruskal ormanı. Her bileşende DFS (veya yığın) ile derinlik ve up[0]. Katla: up[k][v] = up[k-1][up[k-1][v]], mx iki sıçramanın max’ı. Sorgu: derin olanı kaldır, sonra ebeveynler eşleşene kadar ikisini kaldır, max’ı izle.

Yürüyüş. n=3, kenarlar 0-1:2, 1-2:4, 2-0:8. (0,1,2) → max=2 < 2 değil → false. (0,2,5) → 0-1-2 max 4 < 5 → true.

Trade-off. LC 1697 çevrimdışı ikiz (sorguları kenarla sırala). Burada sorgular iç içe, büyüyen UF değil çevrimiçi max-on-path gerekir.

Çözüm

export class DistanceLimitedPathsExist {
  private up: number[][];
  private mx: number[][];
  private depth: number[];
  private LOG: number;
  private comp: number[];

  constructor(n: number, edgeList: number[][]) {
    const edges = edgeList.map((e) => [e[0]!, e[1]!, e[2]!]).sort((a, b) => a[2]! - b[2]!);
    const parent = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
    const adj: [number, number][][] = Array.from({ length: n }, () => []);
    for (const e of edges) {
      const a = find(e[0]!), b = find(e[1]!);
      if (a === b) continue;
      parent[a] = b;
      adj[e[0]!]!.push([e[1]!, e[2]!]);
      adj[e[1]!]!.push([e[0]!, e[2]!]);
    }
    this.comp = Array.from({ length: n }, (_, i) => find(i));

    this.LOG = 1;
    while ((1 << this.LOG) < n) this.LOG++;
    this.up = Array.from({ length: this.LOG }, () => new Array<number>(n).fill(0));
    this.mx = Array.from({ length: this.LOG }, () => new Array<number>(n).fill(0));
    this.depth = new Array<number>(n).fill(-1);

    for (let s = 0; s < n; s++) {
      if (this.depth[s] !== -1) continue;
      this.depth[s] = 0;
      this.up[0]![s] = s;
      const stack = [s];
      while (stack.length) {
        const u = stack.pop()!;
        for (const [v, w] of adj[u]!) {
          if (v === this.up[0]![u] || this.depth[v] !== -1) continue;
          this.depth[v] = this.depth[u]! + 1;
          this.up[0]![v] = u;
          this.mx[0]![v] = w;
          stack.push(v);
        }
      }
    }

    for (let k = 1; k < this.LOG; k++) {
      for (let v = 0; v < n; v++) {
        const mid = this.up[k - 1]![v]!;
        this.up[k]![v] = this.up[k - 1]![mid]!;
        this.mx[k]![v] = Math.max(this.mx[k - 1]![v]!, this.mx[k - 1]![mid]!);
      }
    }
  }

  query(a: number, b: number, limit: number): boolean {
    if (this.comp[a] !== this.comp[b]) return false;
    return this.maxOnPath(a, b) < limit;
  }

  private maxOnPath(a: number, b: number): number {
    if (this.depth[a]! < this.depth[b]!) {
      const t = a; a = b; b = t;
    }
    let ans = 0;
    const diff = this.depth[a]! - this.depth[b]!;
    for (let k = this.LOG - 1; k >= 0; k--) {
      if ((diff >> k) & 1) {
        ans = Math.max(ans, this.mx[k]![a]!);
        a = this.up[k]![a]!;
      }
    }
    if (a === b) return ans;
    for (let k = this.LOG - 1; k >= 0; k--) {
      if (this.up[k]![a] !== this.up[k]![b]) {
        ans = Math.max(ans, this.mx[k]![a]!, this.mx[k]![b]!);
        a = this.up[k]![a]!;
        b = this.up[k]![b]!;
      }
    }
    return Math.max(ans, this.mx[0]![a]!, this.mx[0]![b]!);
  }
}

export class DistanceLimitedPathsExist {
  private up: number[][];
  private mx: number[][];
  private depth: number[];
  private LOG: number;
  private comp: number[];

  constructor(n: number, edgeList: number[][]) {
    const edges = edgeList.map((e) => [e[0]!, e[1]!, e[2]!]).sort((a, b) => a[2]! - b[2]!);
    const parent = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
    const adj: [number, number][][] = Array.from({ length: n }, () => []);
    for (const e of edges) {
      const a = find(e[0]!), b = find(e[1]!);
      if (a === b) continue;
      parent[a] = b;
      adj[e[0]!]!.push([e[1]!, e[2]!]);
      adj[e[1]!]!.push([e[0]!, e[2]!]);
    }
    this.comp = Array.from({ length: n }, (_, i) => find(i));

    this.LOG = 1;
    while ((1 << this.LOG) < n) this.LOG++;
    this.up = Array.from({ length: this.LOG }, () => new Array<number>(n).fill(0));
    this.mx = Array.from({ length: this.LOG }, () => new Array<number>(n).fill(0));
    this.depth = new Array<number>(n).fill(-1);

    for (let s = 0; s < n; s++) {
      if (this.depth[s] !== -1) continue;
      this.depth[s] = 0;
      this.up[0]![s] = s;
      const stack = [s];
      while (stack.length) {
        const u = stack.pop()!;
        for (const [v, w] of adj[u]!) {
          if (v === this.up[0]![u] || this.depth[v] !== -1) continue;
          this.depth[v] = this.depth[u]! + 1;
          this.up[0]![v] = u;
          this.mx[0]![v] = w;
          stack.push(v);
        }
      }
    }

    for (let k = 1; k < this.LOG; k++) {
      for (let v = 0; v < n; v++) {
        const mid = this.up[k - 1]![v]!;
        this.up[k]![v] = this.up[k - 1]![mid]!;
        this.mx[k]![v] = Math.max(this.mx[k - 1]![v]!, this.mx[k - 1]![mid]!);
      }
    }
  }

  query(a: number, b: number, limit: number): boolean {
    if (this.comp[a] !== this.comp[b]) return false;
    return this.maxOnPath(a, b) < limit;
  }

  private maxOnPath(a: number, b: number): number {
    if (this.depth[a]! < this.depth[b]!) {
      const t = a; a = b; b = t;
    }
    let ans = 0;
    const diff = this.depth[a]! - this.depth[b]!;
    for (let k = this.LOG - 1; k >= 0; k--) {
      if ((diff >> k) & 1) {
        ans = Math.max(ans, this.mx[k]![a]!);
        a = this.up[k]![a]!;
      }
    }
    if (a === b) return ans;
    for (let k = this.LOG - 1; k >= 0; k--) {
      if (this.up[k]![a] !== this.up[k]![b]) {
        ans = Math.max(ans, this.mx[k]![a]!, this.mx[k]![b]!);
        a = this.up[k]![a]!;
        b = this.up[k]![b]!;
      }
    }
    return Math.max(ans, this.mx[0]![a]!, this.mx[0]![b]!);
  }
}

Şablon bağlantısı

Kruskal ağacı üretir; kaldırma sorgu yapısı. Kruskal sırasındaki “p ile q’yu bağlayan min kenar” ile aynı darboğaz teoremi.

Yansıma

Kenarları uzunluğa göre Kruskal. Ormanda ikili kaldırma: up[k] ve o sıçramadaki max kenar.
Sorgu, iki düğümü aynı derinliğe çıkarıp max kenarı izler. Max limit’ten küçükse yol var.
Aynı düğüm true. Orman kopuksa bazı çiftler hiç birleşmez. Eşit uzunlukta kenar sırası max’ı değiştirmez.