# 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.

### 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.

## Solution Implementation

``````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``````
``````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) {
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)) {
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) {
67            }
68        }
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``````
``````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``````
``````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)`.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

What's the output of running the following function using input `[30, 20, 10, 100, 33, 12]`?

``````1def fun(arr: List[int]) -> List[int]:
2    import heapq
3    heapq.heapify(arr)
4    res = []
5    for i in range(3):
6        res.append(heapq.heappop(arr))
7    return res
8``````
``````1public static int[] fun(int[] arr) {
2    int[] res = new int[3];
3    PriorityQueue<Integer> heap = new PriorityQueue<>();
4    for (int i = 0; i < arr.length; i++) {
6    }
7    for (int i = 0; i < 3; i++) {
8        res[i] = heap.poll();
9    }
10    return res;
11}
12``````
``````1class HeapItem {
2    constructor(item, priority = item) {
3        this.item = item;
4        this.priority = priority;
5    }
6}
7
8class MinHeap {
9    constructor() {
10        this.heap = [];
11    }
12
13    push(node) {
14        // insert the new node at the end of the heap array
15        this.heap.push(node);
16        // find the correct position for the new node
17        this.bubble_up();
18    }
19
20    bubble_up() {
21        let index = this.heap.length - 1;
22
23        while (index > 0) {
24            const element = this.heap[index];
25            const parentIndex = Math.floor((index - 1) / 2);
26            const parent = this.heap[parentIndex];
27
28            if (parent.priority <= element.priority) break;
29            // if the parent is bigger than the child then swap the parent and child
30            this.heap[index] = parent;
31            this.heap[parentIndex] = element;
32            index = parentIndex;
33        }
34    }
35
36    pop() {
37        const min = this.heap[0];
38        this.heap[0] = this.heap[this.size() - 1];
39        this.heap.pop();
40        this.bubble_down();
41        return min;
42    }
43
44    bubble_down() {
45        let index = 0;
46        let min = index;
47        const n = this.heap.length;
48
49        while (index < n) {
50            const left = 2 * index + 1;
51            const right = left + 1;
52
53            if (left < n && this.heap[left].priority < this.heap[min].priority) {
54                min = left;
55            }
56            if (right < n && this.heap[right].priority < this.heap[min].priority) {
57                min = right;
58            }
59            if (min === index) break;
60            [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61            index = min;
62        }
63    }
64
65    peek() {
66        return this.heap[0];
67    }
68
69    size() {
70        return this.heap.length;
71    }
72}
73
74function fun(arr) {
75    const heap = new MinHeap();
76    for (const x of arr) {
77        heap.push(new HeapItem(x));
78    }
79    const res = [];
80    for (let i = 0; i < 3; i++) {
81        res.push(heap.pop().item);
82    }
83    return res;
84}
85``````