1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree LeetCode Solution
In this guide, you will get 1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree LeetCode Solution with the best time and space complexity. The solution to Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
Problem Statement of Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
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.
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.
Complexity Analysis
Time Complexity: O(n^2\log^* n)
Space Complexity: O(n)
1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree LeetCode Solution in C++
class UnionFind {
public:
UnionFind(int n) : id(n), rank(n) {
iota(id.begin(), id.end(), 0);
}
void unionByRank(int u, int v) {
const int i = find(u);
const int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
int find(int u) {
return id[u] == u ? u : id[u] = find(id[u]);
}
private:
vector<int> id;
vector<int> rank;
};
class Solution {
public:
vector<vector<int>> findCriticalAndPseudoCriticalEdges(
int n, vector<vector<int>>& edges) {
vector<int> criticalEdges;
vector<int> pseudoCriticalEdges;
// Record the index information, so edges[i] := (u, v, weight, index).
for (int i = 0; i < edges.size(); ++i)
edges[i].push_back(i);
// Sort by the weight.
ranges::sort(edges, ranges::less{},
[](const vector<int>& edge) { return edge[2]; });
const int mstWeight = getMSTWeight(n, edges, {}, -1);
for (const vector<int>& edge : edges) {
const int index = edge[3];
// Deleting the `edge` increases the MST's weight or makes the MST
// invalid.
if (getMSTWeight(n, edges, {}, index) > mstWeight)
criticalEdges.push_back(index);
// If an edge can be in any MST, we can always add `edge` to the edge set.
else if (getMSTWeight(n, edges, edge, -1) == mstWeight)
pseudoCriticalEdges.push_back(index);
}
return {criticalEdges, pseudoCriticalEdges};
}
private:
int getMSTWeight(int n, const vector<vector<int>>& edges,
const vector<int>& firstEdge, int deletedEdgeIndex) {
int mstWeight = 0;
UnionFind uf(n);
if (!firstEdge.empty()) {
uf.unionByRank(firstEdge[0], firstEdge[1]);
mstWeight += firstEdge[2];
}
for (const vector<int>& edge : edges) {
const int u = edge[0];
const int v = edge[1];
const int weight = edge[2];
const int index = edge[3];
if (index == deletedEdgeIndex)
continue;
if (uf.find(u) == uf.find(v))
continue;
uf.unionByRank(u, v);
mstWeight += weight;
}
const int root = uf.find(0);
for (int i = 0; i < n; ++i)
if (uf.find(i) != root)
return INT_MAX;
return mstWeight;
}
}; /* code provided by PROGIEZ */
1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree LeetCode Solution in Java
class UnionFind {
public UnionFind(int n) {
id = new int[n];
rank = new int[n];
for (int i = 0; i < n; ++i)
id[i] = i;
}
public void unionByRank(int u, int v) {
final int i = find(u);
final int j = find(v);
if (i == j)
return;
if (rank[i] < rank[j]) {
id[i] = j;
} else if (rank[i] > rank[j]) {
id[j] = i;
} else {
id[i] = j;
++rank[j];
}
}
public int find(int u) {
return id[u] == u ? u : (id[u] = find(id[u]));
}
private int[] id;
private int[] rank;
}
class Solution {
public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
List<Integer> criticalEdges = new ArrayList<>();
List<Integer> pseudoCriticalEdges = new ArrayList<>();
// Record the index information, so edges[i] := (u, v, weight, index).
for (int i = 0; i < edges.length; ++i)
edges[i] = new int[] {edges[i][0], edges[i][1], edges[i][2], i};
// Sort by the weight.
Arrays.sort(edges, (a, b) -> Integer.compare(a[2], b[2]));
final int mstWeight = getMSTWeight(n, edges, new int[] {}, -1);
for (int[] edge : edges) {
final int index = edge[3];
// Deleting the `edge` increases the MST's weight or makes the MST
// invalid.
if (getMSTWeight(n, edges, new int[] {}, index) > mstWeight)
criticalEdges.add(index);
// If an edge can be in any MST, we can always add `edge` to the edge set.
else if (getMSTWeight(n, edges, edge, -1) == mstWeight)
pseudoCriticalEdges.add(index);
}
return List.of(criticalEdges, pseudoCriticalEdges);
}
private int getMSTWeight(int n, int[][] edges, int[] firstEdge, int deletedEdgeIndex) {
int mstWeight = 0;
UnionFind uf = new UnionFind(n);
if (firstEdge.length == 4) {
uf.unionByRank(firstEdge[0], firstEdge[1]);
mstWeight += firstEdge[2];
}
for (int[] edge : edges) {
final int u = edge[0];
final int v = edge[1];
final int weight = edge[2];
final int index = edge[3];
if (index == deletedEdgeIndex)
continue;
if (uf.find(u) == uf.find(v))
continue;
uf.unionByRank(u, v);
mstWeight += weight;
}
final int root = uf.find(0);
for (int i = 0; i < n; ++i)
if (uf.find(i) != root)
return Integer.MAX_VALUE;
return mstWeight;
}
} // code provided by PROGIEZ
1489. Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree LeetCode Solution in Python
class UnionFind:
def __init__(self, n: int):
self.id = list(range(n))
self.rank = [0] * n
def unionByRank(self, u: int, v: int) -> None:
i = self.find(u)
j = self.find(v)
if i == j:
return
if self.rank[i] < self.rank[j]:
self.id[i] = j
elif self.rank[i] > self.rank[j]:
self.id[j] = i
else:
self.id[i] = j
self.rank[j] += 1
def find(self, u: int) -> int:
if self.id[u] != u:
self.id[u] = self.find(self.id[u])
return self.id[u]
class Solution:
def findCriticalAndPseudoCriticalEdges(self, n: int, edges: list[list[int]]) -> list[list[int]]:
criticalEdges = []
pseudoCriticalEdges = []
# Record the index information, so edges[i] := (u, v, weight, index).
for i in range(len(edges)):
edges[i].append(i)
# Sort by the weight.
edges.sort(key=lambda x: x[2])
def getMSTWeight(
firstEdge: list[int],
deletedEdgeIndex: int) -> int | float:
mstWeight = 0
uf = UnionFind(n)
if firstEdge:
uf.unionByRank(firstEdge[0], firstEdge[1])
mstWeight += firstEdge[2]
for u, v, weight, index in edges:
if index == deletedEdgeIndex:
continue
if uf.find(u) == uf.find(v):
continue
uf.unionByRank(u, v)
mstWeight += weight
root = uf.find(0)
if any(uf.find(i) != root for i in range(n)):
return math.inf
return mstWeight
mstWeight = getMSTWeight([], -1)
for edge in edges:
index = edge[3]
# Deleting the `edge` increases the weight of the MST or makes the MST
# invalid.
if getMSTWeight([], index) > mstWeight:
criticalEdges.append(index)
# If an edge can be in any MST, we can always add `edge` to the edge set.
elif getMSTWeight(edge, -1) == mstWeight:
pseudoCriticalEdges.append(index)
return [criticalEdges, pseudoCriticalEdges] # code by PROGIEZ
