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


Problem Description

The problem provides us with a weighted undirected connected graph, where 'n' represents the number of vertices and each edge between any two vertices has a specific weight. Our goal is to identify two types of edges within the minimum spanning tree (MST) of this graph:

  1. Critical edges: These are the edges that, if removed, would result in an increase in the overall weight of the MST or would break the MST such that it no longer spans all vertices. In other words, these edges are essential for maintaining the lowest possible weight of the MST.

  2. Pseudo-critical edges: These are the edges that are not critical but can still be part of some MSTs. They don't appear in every MST, and their inclusion doesn't necessarily make the overall weight of the tree the least possible, but it doesn't break the condition of the MST nor increase its weight beyond the minimum.

The function is expected to return a list of two lists: the first list should contain the indices of all critical edges, and the second list should contain the indices of all pseudo-critical edges.

Intuition

The solution revolves around understanding the properties of an MST in a graph and figuring out the roles of different edges. The main focus is on determining the necessity and replaceability of each edge within the MST.

To find critical and pseudo-critical edges, we perform the following steps:

  1. Initially, sort all the edges based on their weight which will help in applying Kruskal's algorithm to find the minimum spanning tree.

  2. Compute the weight of the MST by using a Union-Find data structure to check if adding an edge would create a cycle. If the edge doesn’t create a cycle, it is added to the running total weight of the MST.

  3. To identify critical edges, we try building an MST for each graph without a specific edge. If the total weight without that edge is more than the original MST or if an MST cannot be formed (there are isolated vertices), we classify this edge as critical.

  4. For pseudo-critical edges, we first include a specific edge and then build the MST with the remaining edges. If the total weight with that edge included is equal to the weight of the original MST, that means this edge is not critical but can be part of MST, hence it is pseudo-critical.

  5. Separate the edges into two categories as per the definitions above and return them as part of the solution.

The given Python code makes use of a class UnionFind to keep track of connected components and a Solution class to implement the logic described for finding critical and pseudo-critical edges.

Solution Approach

The solution uses a combination of sorting, Kruskal's algorithm (a greedy algorithm for finding an MST), and the Union-Find data structure for disjoint-set operations, which helps keep track of the elements in each connected component.

Here's a step-by-step breakdown of how the solution is implemented:

  • Union-Find Implementation: The UnionFind class is crucial for the efficient implementation of Kruskal's algorithm. It includes method find which performs path compression and method union which merges two subsets into one.

  • Kruskal's Algorithm: After sorting the edges by their weight, the solution iteratively checks if adding an edge to the MST would cause a cycle using the Union-Find data structure. If not, the edge is added, and its weight is included in the MST weight.

  • Detecting Critical Edges: For every edge, the code attempts to create an MST without that edge. If the MST cannot span all the vertices (uf.n > 1), or if the total weight of the MST without that edge is greater than the weight of the original MST (k > v), that edge is noted as critical.

  • Finding Pseudo-Critical Edges: To find pseudo-critical edges, each edge is added first and then the rest of the MST is constructed. If including the edge results in an MST with the same total weight as the original (k == v), the edge is marked as pseudo-critical.

This process ensures that all critical and pseudo-critical edges are identified per their definitions in the problem statement.

  • Edge Indexing: Each edge is appended with its original index before sorting to keep track of which edge corresponds to which index as they appear in the original edges array. This is essential for returning the indices of critical and pseudo-critical edges at the end.

The solution returns a list with two sublists, one for each type of edge, indexed as per their appearance in the input list. The Union-Find data structure greatly optimizes disjoint-set operations, which is key to efficiently building the MST and checking the impact of each edge on its total weight.

💪
Level Up Your
Algo Skills

Example Walkthrough

Let's consider a small graph to illustrate the solution approach. Assume our graph has four vertices (1, 2, 3, and 4) and the following five edges with their respective weights:

1Edge 1-2 with weight 1
2Edge 1-3 with weight 2
3Edge 2-3 with weight 3
4Edge 2-4 with weight 4
5Edge 3-4 with weight 5

Let's represent these edges as a list of tuples (u, v, weight, index):

1edges = [
2    (1, 2, 1, 0),
3    (1, 3, 2, 1),
4    (2, 3, 3, 2),
5    (2, 4, 4, 3),
6    (3, 4, 5, 4)
7]

The edge index is added as the fourth item in each tuple for reference.

  1. Initial MST Computation: First, we sort the edges by weight and apply Kruskal's algorithm. This gives us the MST with edges (1-2, 1-3, 2-4) and a total weight of 1 + 2 + 4 = 7.

  2. Critical Edges Detection: Now we need to identify whether any of these edges are critical.

    • Omit edge 1-2: The MST now has edges (1-3, 2-3, 2-4) with a total weight of 2 + 3 + 4 = 9, which is heavier than our original MST. Thus, edge 1-2 is critical.
    • Omit edge 1-3: Without this edge, we're unable to connect all vertices while maintaining a minimum weight. Therefore, edge 1-3 is also critical.
    • Omit edge 2-4: In the absence of this edge, the MST has edges (1-2, 1-3, 3-4) with a total weight of 1 + 2 + 5 = 8, which is heavier. Hence, edge 2-4 is critical as well.
  3. Pseudo-Critical Edges Detection: Since all edges in the MST are critical, there are no possibilities of pseudo-critical edges as pseudo-critical edges are not in every MST but do not increase the total weight.

The result will look like this:

1[
2    [0, 1, 3], // Indices of critical edges
3    []         // Indices of pseudo-critical edges
4]

Each edge was analyzed for its impact on the MST's weight and connectivity, and we separated the critical edges from the pseudo-critical edges. In this case, no pseudo-critical edges were found, and all edges in our original MST were deemed critical.

Python Solution

1from typing import List
2
3class UnionFind:
4    # Initializer creates a parent list for each element and sets the count of clusters
5    def __init__(self, size):
6        self.parents = list(range(size))
7        self.cluster_count = size
8
9    # Merge two sets; if they are already joined, return False
10    def union(self, node1, node2):
11        root1 = self.find(node1)
12        root2 = self.find(node2)
13        if root1 == root2:
14            return False
15        self.parents[root1] = root2
16        self.cluster_count -= 1
17        return True
18
19    # Find the root of the set to which the node belongs, with path compression
20    def find(self, node):
21        if self.parents[node] != node:
22            self.parents[node] = self.find(self.parents[node])
23        return self.parents[node]
24
25
26class Solution:
27    # Method to find the critical and pseudo-critical edges in a minimum spanning tree (MST)
28    def findCriticalAndPseudoCriticalEdges(self, num_nodes: int, edges: List[List[int]]) -> List[List[int]]:
29        # Append the original index to each edge for identification
30        for idx, edge in enumerate(edges):
31            edge.append(idx)
32        # Sort edges by their weight
33        edges.sort(key=lambda x: x[2])
34
35        # Initialize the Union-Find structure
36        union_find = UnionFind(num_nodes)
37        # Compute the value of the MST
38        mst_value = sum(weight for from_node, to_node, weight, _ in edges if union_find.union(from_node, to_node))
39
40        # Initialize list to hold critical and pseudo-critical edges
41        critical_edges, pseudo_critical_edges = [], []
42      
43        # Evaluate each edge to determine if it is critical or pseudo-critical
44        for from_node, to_node, weight, index in edges:
45            # Test if removing the current edge yields a larger MST value or disconnected graph
46            union_find = UnionFind(num_nodes)
47            value_without_edge = sum(edge_weight for edge_from, edge_to, edge_weight, edge_index in edges 
48                                     if edge_index != index and union_find.union(edge_from, edge_to))
49            if union_find.cluster_count > 1 or (union_find.cluster_count == 1 and value_without_edge > mst_value):
50                critical_edges.append(index)
51                continue
52
53            # Test if including the current edge is part of some MST by finding the MST value with the current edge
54            union_find = UnionFind(num_nodes)
55            union_find.union(from_node, to_node)
56            value_with_edge = weight + sum(edge_weight for edge_from, edge_to, edge_weight, edge_index in edges 
57                                           if edge_index != index and union_find.union(edge_from, edge_to))
58
59            # If the value with the current edge equals the original MST value, it's a pseudo-critical edge
60            if value_with_edge == mst_value:
61                pseudo_critical_edges.append(index)
62
63        # Return the results: first the list of critical edges, then the list of pseudo-critical edges
64        return [critical_edges, pseudo_critical_edges]
65

Java Solution

1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.Comparator;
4import java.util.List;
5
6class Solution {
7    public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
8        // Add an edge index to each edge and store it as a new array in the original 'edges' array
9        for (int i = 0; i < edges.length; ++i) {
10            int[] edgeWithIndex = new int[4];
11            System.arraycopy(edges[i], 0, edgeWithIndex, 0, 3);
12            edgeWithIndex[3] = i;
13            edges[i] = edgeWithIndex;
14        }
15      
16        // Sort the edges by their weights
17        Arrays.sort(edges, Comparator.comparingInt(a -> a[2]));
18      
19        // Use Kruskal's algorithm to find the minimum spanning tree (MST) and its weight
20        int totalWeight = 0;
21        UnionFind unionFind = new UnionFind(n);
22        for (int[] edge : edges) {
23            if (unionFind.union(edge[0], edge[1])) {
24                totalWeight += edge[2];
25            }
26        }
27      
28        // Initialize the answer list to hold two lists: one for critical, one for pseudo-critical edges
29        List<List<Integer>> answer = new ArrayList<>();
30        for (int i = 0; i < 2; ++i) {
31            answer.add(new ArrayList<>());
32        }
33      
34        // Check each edge to see if it is critical or pseudo-critical
35        for (int[] edge : edges) {
36            int from = edge[0];
37            int to = edge[1];
38            int weight = edge[2];
39            int index = edge[3];
40          
41            // Check if the edge is critical by trying to form a MST without this edge
42            unionFind = new UnionFind(n);
43            int weightWithoutEdge = 0;
44            for (int[] currentEdge : edges) {
45                if (currentEdge[3] != index && unionFind.union(currentEdge[0], currentEdge[1])) {
46                    weightWithoutEdge += currentEdge[2];
47                }
48            }
49            // If it has more components or the total weight without this edge is greater, it's critical
50            if (unionFind.getN() > 1 || (unionFind.getN() == 1 && weightWithoutEdge > totalWeight)) {
51                answer.get(0).add(index); // Add edge index to critical edges list
52                continue;
53            }
54          
55            // Check if the edge is pseudo-critical by adding it first, then forming the MST
56            unionFind = new UnionFind(n);
57            unionFind.union(from, to);
58            int weightWithEdge = weight;
59            for (int[] currentEdge : edges) {
60                if (currentEdge[3] != index && unionFind.union(currentEdge[0], currentEdge[1])) {
61                    weightWithEdge += currentEdge[2];
62                }
63            }
64            // If adding this edge beforehand does not change the total weight, it's pseudo-critical
65            if (weightWithEdge == totalWeight) {
66                answer.get(1).add(index); // Add edge index to pseudo-critical edges list
67            }
68        }
69        return answer;
70    }
71}
72
73class UnionFind {
74    private int[] parent;
75    private int n;
76
77    public UnionFind(int size) {
78        parent = new int[size];
79        this.n = size;
80        for (int i = 0; i < size; ++i) {
81            parent[i] = i;
82        }
83    }
84
85    public int getN() {
86        return n;
87    }
88
89    public boolean union(int x, int y) {
90        int rootX = find(x);
91        int rootY = find(y);
92        if (rootX == rootY) {
93            return false;
94        }
95        parent[rootX] = rootY;
96        --n; // Decrement the number of components
97        return true;
98    }
99
100    public int find(int x) {
101        if (x != parent[x]) {
102            parent[x] = find(parent[x]); // Path compression
103        }
104        return parent[x];
105    }
106}
107

C++ Solution

1#include <vector>
2#include <numeric>
3#include <algorithm>
4using std::vector;
5using std::sort;
6using std::iota;
7
8// Union-find data structure to help safely combine nodes into disjoint sets.
9class UnionFind {
10public:
11    vector<int> parent; // Parent array to hold the representative element for each set.
12    int setCount; // Count of disjoint sets.
13
14    // Constructor initializes UnionFind with n elements.
15    UnionFind(int n)
16        : setCount(n), parent(vector<int>(n)) {
17        iota(parent.begin(), parent.end(), 0); // Fill parent array with 0, 1, ..., n-1.
18    }
19
20    // Attempt to merge the sets containing elements 'a' and 'b'.
21    bool unite(int a, int b) {
22        a = find(a);
23        b = find(b);
24        if (a == b) return false; // 'a' and 'b' are already in the same set.
25        parent[a] = b; // Merge the sets.
26        --setCount;
27        return true;
28    }
29
30    // Find the representative element (parent) of the set containing 'x'.
31    int find(int x) {
32        if (parent[x] != x) parent[x] = find(parent[x]); // Path compression.
33        return parent[x];
34    }
35};
36
37class Solution {
38public:
39    // Main function to find critical and pseudo-critical edges in a graph.
40    vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
41        // Add the index of the edge to the end of each edge's vector to keep track of them after sorting.
42        for (int i = 0; i < edges.size(); ++i) edges[i].push_back(i);
43      
44        // Sort edges by weight. If weights are equal, it sorts by the indices added above.
45        sort(edges.begin(), edges.end(), [](const auto& a, const auto& b) { return a[2] < b[2]; });
46
47        int minimumSpanningTreeWeight = 0; // To hold the total weight of the minimum spanning tree.
48        UnionFind uf(n); // Create an instance of UnionFind.
49      
50        // Create the minimum spanning tree and calculate its weight.
51        for (auto& edge : edges) {
52            if (uf.unite(edge[0], edge[1])) minimumSpanningTreeWeight += edge[2];
53        }
54      
55        vector<vector<int>> result(2); // Resultant vector to hold critical and pseudo-critical edges.
56      
57        for (auto& edge : edges) {
58            int from = edge[0], to = edge[1], weight = edge[2], index = edge[3];
59            UnionFind ufWithoutEdge(n);
60            int weightWithoutEdge = 0;
61          
62            // Check if removing the edge increases total weight of MST (making it critical).
63            for (auto& nextEdge : edges) {
64                if (nextEdge[3] != index && ufWithoutEdge.unite(nextEdge[0], nextEdge[1]))
65                    weightWithoutEdge += nextEdge[2];
66            }
67          
68            if (ufWithoutEdge.setCount > 1 || (ufWithoutEdge.setCount == 1 && weightWithoutEdge > minimumSpanningTreeWeight)) {
69                result[0].push_back(index); // Edge is critical.
70                continue;
71            }
72          
73            // Check if including the edge doesn't increase total weight of MST (making it pseudo-critical).
74            UnionFind ufWithEdge(n);
75            ufWithEdge.unite(from, to);
76            int weightWithEdge = weight;
77          
78            for (auto& nextEdge : edges) {
79                if (nextEdge[3] != index && ufWithEdge.unite(nextEdge[0], nextEdge[1]))
80                    weightWithEdge += nextEdge[2];
81            }
82          
83            if (weightWithEdge == minimumSpanningTreeWeight) {
84                result[1].push_back(index); // Edge is pseudo-critical.
85            }
86        }
87      
88        return result;
89    }
90};
91

Typescript Solution

1// Represents the parent array to hold the representative element for each set.
2let parent: number[];
3
4// Represents the count of disjoint sets.
5let setCount: number;
6
7// Initialize UnionFind with n elements.
8function initializeUnionFind(n: number): void {
9  setCount = n;
10  parent = Array.from({ length: n }, (_, index) => index);
11}
12
13// Attempt to merge the sets containing elements 'a' and 'b'.
14function unite(a: number, b: number): boolean {
15  a = find(a);
16  b = find(b);
17  if (a === b) return false; // 'a' and 'b' are already in the same set.
18  parent[a] = b; // Merge the sets.
19  setCount--;
20  return true;
21}
22
23// Find the representative element (parent) of the set containing 'x'.
24function find(x: number): number {
25  if (parent[x] !== x) parent[x] = find(parent[x]); // Path compression.
26  return parent[x];
27}
28
29// Main function to find critical and pseudo-critical edges in a graph
30function findCriticalAndPseudoCriticalEdges(n: number, edges: number[][]): number[][] {
31  // Add the index of the edge to the end of each edge's array to keep track of them after sorting.
32  edges.forEach((edge, index) => {
33    edge.push(index);
34  });
35
36  // Sort edges by weight. If weights are equal, it sorts by the added indices.
37  edges.sort((a, b) => a[2] - b[2]);
38
39  // To hold the total weight of the minimum spanning tree (MST).
40  let minimumSpanningTreeWeight = 0;
41
42  // Create an instance of UnionFind.
43  initializeUnionFind(n);
44
45  // Create the minimum spanning tree (MST) and calculate its weight.
46  edges.forEach(edge => {
47    if (unite(edge[0], edge[1])) {
48      minimumSpanningTreeWeight += edge[2];
49    }
50  });
51
52  // Resultant array to hold critical and pseudo-critical edges.
53  const result: number[][] = [[], []];
54
55  edges.forEach(edge => {
56    const [from, to, weight, index] = edge;
57    initializeUnionFind(n); // Reset UnionFind without the current edge.
58    let weightWithoutEdge = 0;
59
60    // Check if removing the edge increases the total weight of the MST (making it critical).
61    edges.forEach(nextEdge => {
62      if (nextEdge[3] !== index && unite(nextEdge[0], nextEdge[1])) {
63        weightWithoutEdge += nextEdge[2];
64      }
65    });
66
67    if (setCount > 1 || (setCount === 1 && weightWithoutEdge > minimumSpanningTreeWeight)) {
68      result[0].push(index); // Edge is critical.
69    } else {
70      // Check if including the edge doesn't increase the total weight of the MST (making it pseudo-critical).
71      initializeUnionFind(n);
72      unite(from, to);
73      let weightWithEdge = weight;
74
75      edges.forEach(nextEdge => {
76        if (nextEdge[3] !== index && unite(nextEdge[0], nextEdge[1])) {
77          weightWithEdge += nextEdge[2];
78        }
79      });
80
81      if (weightWithEdge === minimumSpanningTreeWeight) {
82        result[1].push(index); // Edge is pseudo-critical.
83      }
84    }
85  });
86
87  return result;
88}
89

Time and Space Complexity

Time Complexity

The given code defines a UnionFind class used for disjoint-set operations and a Solution class that finds critical and pseudo-critical edges in a graph.

  • The UnionFind class has two methods, union and find, each call of union can result in a call to find. The find function uses path compression which has an amortized time complexity close to O(1) for each call.

  • The Solution.findCriticalAndPseudoCriticalEdges method initializes the UnionFind instance once with O(n) where n is the number of vertices in the graph.

  • The edges are then sorted, which takes O(E log E) time, where E is the number of edges.

  • The initial MST value v is computed with O(E) calls to union, which takes near O(E) time.

  • In the worst-case scenario for finding critical and pseudo-critical edges, the method iterates over each of the edges and for each edge:

    • The method creates a new UnionFind instance which takes O(n) time.
    • Then it iterates over all the edges (minus one) to compute the total weight excluding the current edge, with each iteration making a call to union. This takes up to O(E) calls to union per edge, therefore O(E^2) for all edges.
  • Additionally, for each non-critical edge, there is another UnionFind instance creation plus E calls to union which is also O(E) calls per edge, adding O(E^2) for all edges.

Thus, putting it all together, we get: O(E log E) (for sorting) + O(E) (for initial MST) + 2*O(E^2) (for checking each edge for critical and pseudo-critical) = O(E log E + E + 2*E^2) = O(E^2) since E^2 dominates E log E and E.

The overall time complexity is O(E^2), since the E^2 term dominates.

Space Complexity

The space complexity of the code is determined by the storage of the following components:

  • The UnionFind data structure uses an array p of size n, which takes O(n) space.

  • The edges list is augmented with index information, but it does not increase the asymptotic space complexity; it still takes O(E) space.

  • The ans list which contains two lists to hold the critical and pseudo-critical edges, in the worst case could hold all edges, making it O(E) space.

  • Local variables inside the loop have constant space usage and do not contribute to the space complexity in terms of n or E.

The space required for the UnionFind instances inside the loops does not accumulate since they are created anew for each iteration.

Therefore, the overall space complexity is the maximum space used at any point in time, which is the sum of individual parts that contribute to the space complexity. This results in O(n + E).

The overall space complexity is O(n + E).

😈
Become an
Algo Monster

Got a question? Ask the Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


TA 👨‍🏫