Sponsored
Sponsored
This approach involves using Kruskal's algorithm to find the Minimum Spanning Tree. First, sort all edges by weight. Then, use a Union-Find data structure to maintain and check connectivity of the nodes as edges are added to the MST. Critical edges are those whose exclusion from the MST will increase its total weight, whereas pseudo-critical edges are those that can be in any MST when forced to be present.
The time complexity is O(E log E), where E is the number of edges, mainly due to sorting edges. Space complexity is O(V), where V is the number of vertices, due to the Union-Find structure.
1from collections import defaultdict
2
3class UnionFind:
4 def __init__(self, size):
5 self.parent = list(range(size))
6 self.rank = [1] * size
7
8 def find(self, u):
9 if self.parent[u] != u:
10 self.parent[u] = self.find(self.parent[u])
11 return self.parent[u]
12
13 def union(self, u, v):
14 rootU = self.find(u)
15 rootV = self.find(v)
16 if rootU != rootV:
17 if self.rank[rootU] > self.rank[rootV]:
18 self.parent[rootV] = rootU
19 elif self.rank[rootU] < self.rank[rootV]:
20 self.parent[rootU] = rootV
21 else:
22 self.parent[rootV] = rootU
23 self.rank[rootU] += 1
24 return rootU != rootV
25
26 def connected(self, u, v):
27 return self.find(u) == self.find(v)
28
29
30class Solution:
31 def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
32 edges_with_index = [(wt, u, v, i) for i, (u, v, wt) in enumerate(edges)]
33 edges_with_index.sort() # Sort by weight
34
35 def kruskal(n, edges, include=-1, exclude=-1):
36 uf = UnionFind(n)
37 mst_weight = 0
38 edges_used = 0
39 if include != -1:
40 wt, u, v, i = edges[include]
41 if uf.union(u, v):
42 mst_weight += wt
43 edges_used += 1
44 for i, (wt, u, v, idx) in enumerate(edges):
45 if i == exclude:
46 continue
47 if uf.union(u, v):
48 mst_weight += wt
49 edges_used += 1
50 if edges_used == n - 1:
51 break
52 return mst_weight if edges_used == n - 1 else float('inf')
53
54 min_mst_weight = kruskal(n, edges_with_index)
55 critical = []
56 pseudo_critical = []
57
58 for i in range(len(edges_with_index)):
59 if kruskal(n, edges_with_index, exclude=i) > min_mst_weight:
60 critical.append(edges_with_index[i][3])
61 elif kruskal(n, edges_with_index, include=i) == min_mst_weight:
62 pseudo_critical.append(edges_with_index[i][3])
63 return [critical, pseudo_critical]This solution uses Kruskal's algorithm for MST construction. We first sort edges by weight, then use a Union-Find data structure to track connected components as we build the MST. Each edge is checked to see if its exclusion increases the MST weight, which determines if it's critical. For pseudo-critical edges, we include them initially and check if they can form an MST of the same weight. The complexity involves sorting and iterating over the edges.
This approach leverages Kruskal's algorithm to build MSTs while testing each edge's criticality and pseudo-criticality. We initially use Kruskal's algorithm to determine the MST and its weight without any edge removal. We then experiment with excluding and mandatorily including each edge to ascertain its nature: critical or pseudo-critical.
Steps:
Time Complexity: O(E^2 * log(E)) where E is the number of edges, due to sorting and constructing MST for each edge.
Space Complexity: O(E + V) where E is the number of edges and V is the number of vertices used for storing edges and union-find data structure.
1class
This approach focuses on constructing subsets of edges that definitely belong or don't belong in the MST. By manipulating combinations of edges and recalculating the MST weight, this approach checks the necessity of each edge.
Steps:
Time Complexity: O(E^2 * log(E)) due to sorting edges and iterating for each edge's condition.
Space Complexity: O(E + V) for storing edges and union-find structure during operations.
1import java.util.
This JavaScript solution defines a Union-Find class for performing union and find operations, essential for Kruskal's algorithm. Two checks are performed for each edge: one to ascertain if its exclusion raises the MST weight (indicative of criticality), and another to observe if a forced inclusion keeps the MST weight constant (demonstrating pseudo-criticality). Each of these operations helps distinguish between critical and pseudo-critical edges effectively.
This Java solution employs a UnionFind class to facilitate connectivity checks across nodes in a graph for Kruskal's algorithm. By recalculating MST weights with various inclusion/exclusion scenarios, the solution effectively identifies edges' criticality. The use of sorting and priority checks makes the solution performant even with higher complexity edge cases. The approach embodies classic algorithmic techniques adapted for the problem's specific needs.