Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Find Critical and Pseudo-Critical Edges in MST

Problem (restated)

Weighted undirected graph. Return [critical, pseudoCritical] — edge indices. Critical: deleting it raises MST weight (or disconnects). Pseudo-critical: not critical, but some MST includes it.

Intuition

n ≤ 100, so rerun Kruskal per edge. Baseline MST weight base. Exclude i: if cost > base → critical. Force i first: if cost == base and not critical → pseudo.

Approaches

Kruskal, force / exclude

Unverified

Time O(E² α(n))Space O(n)

Idea. Tag each edge with its original index, sort a copy. mst(exclude, force) unions the forced edge first (if any), then the sorted list, skipping the excluded index. Disconnected → ∞.

Walkthrough. Five vertices, several weight-1/2/3 edges: the two weight-1 edges are unique bridges (critical); several weight-2/3 edges sit on alternate MSTs (pseudo).

Trade-offs. Keep original indices — the answer is not endpoints. Forcing an edge that closes a cycle of cheaper edges yields cost > base, so it is neither.

Solution

export function findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {
  const indexed = edges.map((e, i) => [e[0]!, e[1]!, e[2]!, i]);
  indexed.sort((a, b) => a[2]! - b[2]!);

  const mst = (exclude: number, force: number): number => {
    const parent = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
    let cost = 0, used = 0;
    const uni = (u: number, v: number, w: number): boolean => {
      const a = find(u), b = find(v);
      if (a === b) return false;
      parent[a] = b;
      cost += w;
      used++;
      return true;
    };
    if (force >= 0) {
      const e = edges[force]!;
      uni(e[0]!, e[1]!, e[2]!);
    }
    for (const e of indexed) {
      if (e[3] === exclude || e[3] === force) continue;
      uni(e[0]!, e[1]!, e[2]!);
      if (used === n - 1) break;
    }
    return used === n - 1 ? cost : Infinity;
  };

  const base = mst(-1, -1);
  const critical: number[] = [];
  const pseudo: number[] = [];
  for (let i = 0; i < edges.length; i++) {
    if (mst(i, -1) > base) critical.push(i);
    else if (mst(-1, i) === base) pseudo.push(i);
  }
  return [critical, pseudo];
}

export function findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {
  const indexed = edges.map((e, i) => [e[0]!, e[1]!, e[2]!, i]);
  indexed.sort((a, b) => a[2]! - b[2]!);

  const mst = (exclude: number, force: number): number => {
    const parent = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => (parent[x] === x ? x : (parent[x] = find(parent[x]!)));
    let cost = 0, used = 0;
    const uni = (u: number, v: number, w: number): boolean => {
      const a = find(u), b = find(v);
      if (a === b) return false;
      parent[a] = b;
      cost += w;
      used++;
      return true;
    };
    if (force >= 0) {
      const e = edges[force]!;
      uni(e[0]!, e[1]!, e[2]!);
    }
    for (const e of indexed) {
      if (e[3] === exclude || e[3] === force) continue;
      uni(e[0]!, e[1]!, e[2]!);
      if (used === n - 1) break;
    }
    return used === n - 1 ? cost : Infinity;
  };

  const base = mst(-1, -1);
  const critical: number[] = [];
  const pseudo: number[] = [];
  for (let i = 0; i < edges.length; i++) {
    if (mst(i, -1) > base) critical.push(i);
    else if (mst(-1, i) === base) pseudo.push(i);
  }
  return [critical, pseudo];
}

Template connection

Kruskal as a subroutine. Same UF as LC 1135, called O(E) times with a filter.

Reflection

Build the base MST first. Excluding an edge makes it critical when the cost rises or the graph disconnects. Forcing it makes it pseudo-critical only when the cost stays equal to the base and the edge was not critical.
An edge is written in one list or the other. An edge that closes a cheaper cycle is in neither.
A disconnected run is infinite. The answer is the original edge index, not the endpoints. n = 1 has no edges.