1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree

Description

Given a weighted undirected connected graph with n vertices numbered from 0 to n - 1, and an array edges where edges[i] = [ai, bi, weighti] represents a bidirectional and weighted edge between nodes ai and bi. A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the minimum possible total edge weight.

Find all the critical and pseudo-critical edges in the given graph's minimum spanning tree (MST). An MST edge whose deletion from the graph would cause the MST weight to increase is called a critical edge. On the other hand, a pseudo-critical edge is that which can appear in some MSTs but not all.

Note that you can return the indices of the edges in any order.

 

Example 1:

Input: n = 5, edges = [[0,1,1],[1,2,1],[2,3,2],[0,3,2],[0,4,3],[3,4,3],[1,4,6]]
Output: [[0,1],[2,3,4,5]]
Explanation: The figure above describes the graph.
The following figure shows all the possible MSTs:

Notice that the two edges 0 and 1 appear in all MSTs, therefore they are critical edges, so we return them in the first list of the output.
The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges. We add them to the second list of the output.

Example 2:

Input: n = 4, edges = [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: [[],[0,1,2,3]]
Explanation: We can observe that since all 4 edges have equal weight, choosing any 3 edges from the given 4 will yield an MST. Therefore all 4 edges are pseudo-critical.

 

Constraints:

• 2 <= n <= 100
• 1 <= edges.length <= min(200, n * (n - 1) / 2)
• edges[i].length == 3
• 0 <= ai < bi < n
• 1 <= weighti <= 1000
• All pairs (ai, bi) are distinct.

 

Solutions

Solution: Kruskal Algorithm

• Time complexity: O(eloge+e²)
• Space complexity: O(n+e)
  • e: edges.length

 

JavaScript

/**
 * @param {number} n
 * @param {number[][]} edges
 * @return {number[][]}
 */
const findCriticalAndPseudoCriticalEdges = function (n, edges) {
  const group = Array.from({ length: n });
  const rank = Array.from({ length: n });

  edges = edges.map((edge, index) => [...edge, index]);
  edges.sort((a, b) => a[2] - b[2]);

  const find = node => {
    if (group[node] !== node) {
      group[node] = find(group[node]);
    }

    return group[node];
  };

  const union = (a, b) => {
    const groupA = find(a);
    const groupB = find(b);

    if (groupA === groupB) return false;

    if (rank[groupA] > rank[groupB]) {
      group[groupB] = groupA;
    } else if (rank[groupA] < rank[groupB]) {
      group[groupA] = groupB;
    } else {
      group[groupB] = groupA;
      rank[groupA] += 1;
    }

    return true;
  };

  const restUnion = () => {
    for (let node = 0; node < n; node++) {
      group[node] = node;
      rank[node] = 0;
    }
  };

  const getMSTWeight = (deleteIndex = -1, outset) => {
    let mstWeight = 0;
    let useEdges = 0;

    restUnion();

    if (outset) {
      const [a, b, weight] = outset;

      union(a, b);
      mstWeight += weight;
      useEdges += 1;
    }

    for (const [a, b, weight, index] of edges) {
      if (deleteIndex === index || !union(a, b)) continue;

      mstWeight += weight;
      useEdges += 1;
    }

    return useEdges === n - 1 ? mstWeight : Number.MAX_SAFE_INTEGER;
  };

  const criticalEdges = [];
  const pseudoCriticalEdges = [];
  const mstWeight = getMSTWeight();

  for (const edge of edges) {
    const [a, b, weight, index] = edge;

    if (getMSTWeight(index) > mstWeight) {
      criticalEdges.push(index);
    } else if (getMSTWeight(-1, edge) === mstWeight) {
      pseudoCriticalEdges.push(index);
    }
  }

  return [criticalEdges, pseudoCriticalEdges];
};