Editorial
Core insight
Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree · Graph Traversal Patterns (DFS & BFS)
Core Insight for Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
The optimal solution combines Kruskal's algorithm with Tarjan's Bridge-Finding algorithm.
The core intuition relies on how Kruskal's algorithm builds an MST: it sorts edges by weight and processes them in non-decreasing order. Let's focus on a "batch" of edges that all have the exact same weight .
Before processing this batch, we have a set of connected components formed by all edges with weights less than . The edges in the current batch will connect these components together.
Visualizing the Component Graph: Imagine shrinking each existing connected component into a single "super-node." The edges in our current batch now form a temporary graph connecting these super-nodes.
- Critical Edges: If an edge in this temporary graph is a bridge, it must be included to connect the components. If we don't take it, we'd need a heavier edge later to connect them, violating the MST property. Thus, bridges in this batch-graph are critical edges.
- Pseudo-Critical Edges: If an edge connects two distinct super-nodes but is not a bridge (i.e., it is part of a cycle within this batch), we can take it, but we don't have to (we could take another edge on the cycle). Thus, non-bridge edges in the batch-graph are pseudo-critical.
- Loops: If an edge connects a super-node to itself (both endpoints are already in the same component), it is useless and discarded.
The Invariant:
By running Tarjan's algorithm on the subgraph formed only by the current batch of equal-weight edges (acting on the component super-nodes), we can strictly classify them using the low-link values derived from DFS.
Deep dive
Full breakdown
Full reasoning, pitfalls, and implementation flow
LeetCode 1489: Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree Solution & Explanation
Problem Overview
TL;DR: Use Kruskal's algorithm to process edges by weight groups, then apply Tarjan's Bridge-Finding algorithm within each group to identify critical edges (bridges) and pseudo-critical edges (non-bridge cycle edges).
The problem asks us to classify every edge in a weighted, undirected connected graph into one of three categories based on its role in forming a Minimum Spanning Tree (MST):
- Critical: The edge appears in every possible MST. Removing it increases the MST weight.
- Pseudo-Critical: The edge appears in some MSTs but not all. It can be replaced by another edge of equal weight without changing the total MST weight.
- Neither: The edge is never part of any MST (usually because it forms a cycle with lighter edges).
This is a popular interview question that tests deep understanding of MST properties and graph connectivity algorithms like Tarjan's.
Brute Force Approach for Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree
A naive approach relies on the definition of critical and pseudo-critical edges by simulating the MST construction repeatedly.
- Calculate Base MST Weight: Run a standard MST algorithm (like Kruskal's or Prim's) to find the minimum total weight, .
- Check Criticality: For every edge :
- Temporarily delete edge from the graph.
- Recalculate the MST weight.
- If the graph becomes disconnected or the new weight , edge is critical.
- Check Pseudo-Criticality: If an edge is not critical:
- Force-include edge in the MST (add it first, then run Kruskal's for the rest).
- If the resulting weight equals , edge is pseudo-critical.
Pseudo-code:
1base_mst = kruskal(all_edges)
2for edge in all_edges:
3 # Check Critical
4 weight_without = kruskal(all_edges excluding edge)
5 if weight_without > base_mst:
6 mark_critical(edge)
7 continue
8
9 # Check Pseudo-Critical
10 weight_with = kruskal(force_include(edge))
11 if weight_with == base_mst:
12 mark_pseudo_critical(edge)Complexity Analysis:
- Time Complexity: We run Kruskal's algorithm ( or ) roughly times. Total complexity is or .
- Why it fails: While this passes for small , it scales poorly. For dense graphs where , this becomes , which is unacceptable for larger constraints typically seen in system design or harder algorithm problems. It lacks the elegance of a single-pass structural analysis.
Algorithm Strategy: Graph Traversal Patterns (DFS & BFS)
-
Initialization:
- Add the original index to each edge for tracking.
- Sort all edges by weight.
- Initialize a Disjoint Set Union (DSU) structure to manage connected components.
- Prepare lists for critical and pseudo-critical edges.
-
Batch Processing:
- Iterate through the sorted edges. Identify a "batch" of edges that share the same weight.
- For each batch:
- Build the Graph: Construct an adjacency list where nodes are the current component identifiers (roots in DSU) of the edge endpoints. Only include edges that connect different components.
- Find Bridges (Tarjan's): Run Tarjan's bridge-finding algorithm on this temporary graph.
- Track
discoveryandlowtimes. - Pass the edge index to the DFS to handle parallel edges (multiple edges between the same two components).
- Track
- Classify:
- If an edge is a bridge, add it to the Critical list.
- If an edge connects two different components but is not a bridge, add it to the Pseudo-Critical list.
- Union: After classification, perform the standard DSU
unionoperation for all edges in the batch to merge components permanently.
-
Tarjan's Logic Refresher:
- Maintain a global timer.
discovery[u]: Time at which nodeuwas first visited.low[u]: Lowest discovery time reachable fromu(including via back-edges).- An edge
(u, v)is a bridge iflow[v] > discovery[u].
Execution Flow
Let's trace the logic with a simplified example.
Edges (sorted): e1(w=1), e2(w=1), e3(w=1), e4(w=2).
-
Batch 1 (Weight 1): Contains
e1,e2,e3.- Initially, each node is its own component.
- We build a graph with these 3 edges.
- Scenario:
e1,e2,e3form a triangle (cycle) between nodes 0, 1, 2. - Tarjan's Execution:
- DFS starts at 0. Visits 1 via
e1. - From 1, visits 2 via
e2. - From 2, sees 0 via
e3. This is a back-edge.low[2]updates todiscovery[0]. - Recursion unwinds.
low[1]updates fromlow[2].low[0]updates. - No edge satisfies
low[child] > discovery[parent].
- DFS starts at 0. Visits 1 via
- Result: No bridges found. All 3 edges connect distinct components but aren't bridges.
- Classification:
e1,e2,e3are Pseudo-Critical. - Union: Merge sets containing 0, 1, 2.
-
Batch 2 (Weight 2): Contains
e4.- Assume
e4connects node 2 to node 3. - Node 2 is in component
{0,1,2}. Node 3 is in{3}. - Build graph: Edge between SuperNode A and SuperNode B.
- Tarjan's Execution:
- DFS visits A, then B. No back-edges.
- Edge satisfies
low[B] > discovery[A].
- Result:
e4is a bridge. - Classification:
e4is Critical. - Union: Merge all nodes.
- Assume
Proof of Correctness
The correctness hinges on the Cut Property and Cycle Property of MSTs.
- Critical Edges (Cut Property): An edge is critical if it is a bridge in the graph formed by contracting all edges lighter than it. If it is a bridge, it is the only edge crossing the cut between two components at that weight. It must be included to ensure connectivity.
- Pseudo-Critical Edges (Cycle Property): If an edge is not a bridge but connects two previously disconnected components, it is part of a cycle formed by edges of the same weight. By the cycle property, we can include at most edges from a simple cycle of length . Since all edges on this cycle have the same weight, any subset that connects the vertices is valid. Thus, the edge can be included (making it pseudo-critical) but isn't mandatory.
The algorithm correctly identifies these topological properties using Tarjan's DFS on the component graph.
Pattern Reuse Notes
The logic of finding bridges and articulation points is directly applicable to:
- LeetCode 1192: Critical Connections in a Network - This is the standard "Find Bridges" problem. The core Tarjan's implementation is identical to the one used inside the batch processing here.
Both problems require mastering Tarjan's low-link values to detect structural vulnerabilities (bridges) in a graph.
Feynman coach · Before you peek at the code
Can you explain the core insight in your own words?
If you can explain it before reading code, you’re far more likely to recall it under interview pressure.
Loading your attempt…
Reference Implementation
C++ Solution for LeetCode 1489
1class Solution {
2 struct DSU {
3 vector<int> parent;
4 DSU(int n) {
5 parent.resize(n);
6 iota(parent.begin(), parent.end(), 0);
7 }
8 int find(int x) {
9 if (parent[x] != x) parent[x] = find(parent[x]);
10 return parent[x];
11 }
12 void unite(int x, int y) {
13 parent[find(x)] = find(y);
14 }
15 };
16
17 int timer;
18 vector<int> disc, low;
19 vector<vector<pair<int, int>>> adj; // adj[u] = {v, edge_index}
20 vector<int> critical, pseudo;
21
22 void tarjan(int u, int p_edge_idx) {
23 disc[u] = low[u] = ++timer;
24 for (auto& edge : adj[u]) {
25 int v = edge.first;
26 int idx = edge.second;
27
28 if (idx == p_edge_idx) continue; // Don't go back through the same edge
29
30 if (disc[v]) {
31 low[u] = min(low[u], disc[v]);
32 } else {
33 tarjan(v, idx);
34 low[u] = min(low[u], low[v]);
35 if (low[v] > disc[u]) {
36 // This edge is a bridge
37 critical.push_back(idx);
38 }
39 }
40 }
41 }
42
43public:
44 vector<vector<int>> findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& edges) {
45 // Append original index to edges: {u, v, w, index}
46 for (int i = 0; i < edges.size(); ++i) {
47 edges[i].push_back(i);
48 }
49
50 // Sort by weight
51 sort(edges.begin(), edges.end(), [](const vector<int>& a, const vector<int>& b) {
52 return a[2] < b[2];
53 });
54
55 DSU dsu(n);
56 disc.assign(n, 0);
57 low.assign(n, 0);
58 adj.resize(n);
59
60 // Use a set or boolean array to quickly check if an index is critical later
61 vector<bool> is_critical(edges.size(), false);
62
63 int i = 0;
64 while (i < edges.size()) {
65 int j = i;
66 // Find the end of the current weight batch
67 while (j < edges.size() && edges[j][2] == edges[i][2]) {
68 j++;
69 }
70
71 // Build graph for this batch
72 // Nodes are component representatives
73 // We only care about edges connecting different components
74 vector<int> unique_nodes;
75 for (int k = i; k < j; ++k) {
76 int u = dsu.find(edges[k][0]);
77 int v = dsu.find(edges[k][1]);
78
79 if (u != v) {
80 adj[u].push_back({v, edges[k][3]});
81 adj[v].push_back({u, edges[k][3]});
82 unique_nodes.push_back(u);
83 unique_nodes.push_back(v);
84 }
85 }
86
87 // Run Tarjan's on the component graph
88 timer = 0;
89 // Clear previous criticals for this batch specifically to mark them
90 int pre_critical_count = critical.size();
91
92 // Sort and remove duplicates to iterate nodes efficiently
93 sort(unique_nodes.begin(), unique_nodes.end());
94 unique_nodes.erase(unique(unique_nodes.begin(), unique_nodes.end()), unique_nodes.end());
95
96 for (int node : unique_nodes) {
97 if (!disc[node]) {
98 tarjan(node, -1);
99 }
100 }
101
102 // Mark critical edges found in this batch
103 for (int k = pre_critical_count; k < critical.size(); ++k) {
104 is_critical[critical[k]] = true;
105 }
106
107 // Identify Pseudo-Critical Edges
108 // An edge is pseudo-critical if it connects different components but is NOT critical
109 for (int k = i; k < j; ++k) {
110 int u = dsu.find(edges[k][0]);
111 int v = dsu.find(edges[k][1]);
112 int idx = edges[k][3];
113
114 if (u != v && !is_critical[idx]) {
115 pseudo.push_back(idx);
116 }
117 }
118
119 // Unite components and cleanup for next batch
120 for (int k = i; k < j; ++k) {
121 dsu.unite(edges[k][0], edges[k][1]);
122 }
123
124 // Reset Tarjan structures for next batch
125 for (int node : unique_nodes) {
126 adj[node].clear();
127 disc[node] = 0;
128 low[node] = 0;
129 }
130
131 i = j;
132 }
133
134 sort(critical.begin(), critical.end());
135 sort(pseudo.begin(), pseudo.end());
136 return {critical, pseudo};
137 }
138};Java Solution for LeetCode 1489
1import java.util.*;
2
3class Solution {
4 class DSU {
5 int[] parent;
6 DSU(int n) {
7 parent = new int[n];
8 for (int i = 0; i < n; i++) parent[i] = i;
9 }
10 int find(int x) {
11 if (parent[x] != x) parent[x] = find(parent[x]);
12 return parent[x];
13 }
14 void unite(int x, int y) {
15 parent[find(x)] = find(y);
16 }
17 }
18
19 private int timer;
20 private int[] disc, low;
21 private List<List<int[]>> adj;
22 private List<Integer> critical = new ArrayList<>();
23 private List<Integer> pseudo = new ArrayList<>();
24 private boolean[] isCritical;
25
26 private void tarjan(int u, int pEdgeIdx) {
27 disc[u] = low[u] = ++timer;
28 for (int[] edge : adj.get(u)) {
29 int v = edge[0];
30 int idx = edge[1];
31
32 if (idx == pEdgeIdx) continue;
33
34 if (disc[v] != 0) {
35 low[u] = Math.min(low[u], disc[v]);
36 } else {
37 tarjan(v, idx);
38 low[u] = Math.min(low[u], low[v]);
39 if (low[v] > disc[u]) {
40 critical.add(idx);
41 isCritical[idx] = true;
42 }
43 }
44 }
45 }
46
47 public List<List<Integer>> findCriticalAndPseudoCriticalEdges(int n, int[][] edges) {
48 int m = edges.length;
49 int[][] sortedEdges = new int[m][4];
50 for (int i = 0; i < m; i++) {
51 sortedEdges[i][0] = edges[i][0];
52 sortedEdges[i][1] = edges[i][1];
53 sortedEdges[i][2] = edges[i][2];
54 sortedEdges[i][3] = i; // Original index
55 }
56
57 Arrays.sort(sortedEdges, (a, b) -> Integer.compare(a[2], b[2]));
58
59 DSU dsu = new DSU(n);
60 disc = new int[n];
61 low = new int[n];
62 adj = new ArrayList<>();
63 for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
64 isCritical = new boolean[m];
65
66 int i = 0;
67 while (i < m) {
68 int j = i;
69 while (j < m && sortedEdges[j][2] == sortedEdges[i][2]) j++;
70
71 Set<Integer> uniqueNodes = new HashSet<>();
72
73 // Build graph
74 for (int k = i; k < j; k++) {
75 int u = dsu.find(sortedEdges[k][0]);
76 int v = dsu.find(sortedEdges[k][1]);
77
78 if (u != v) {
79 adj.get(u).add(new int[]{v, sortedEdges[k][3]});
80 adj.get(v).add(new int[]{u, sortedEdges[k][3]});
81 uniqueNodes.add(u);
82 uniqueNodes.add(v);
83 }
84 }
85
86 timer = 0;
87 for (int node : uniqueNodes) {
88 if (disc[node] == 0) tarjan(node, -1);
89 }
90
91 for (int k = i; k < j; k++) {
92 int u = dsu.find(sortedEdges[k][0]);
93 int v = dsu.find(sortedEdges[k][1]);
94 int idx = sortedEdges[k][3];
95
96 if (u != v && !isCritical[idx]) {
97 pseudo.add(idx);
98 }
99 }
100
101 // Cleanup and Union
102 for (int k = i; k < j; k++) {
103 dsu.unite(sortedEdges[k][0], sortedEdges[k][1]);
104 }
105
106 for (int node : uniqueNodes) {
107 adj.get(node).clear();
108 disc[node] = 0;
109 low[node] = 0;
110 }
111
112 i = j;
113 }
114
115 return Arrays.asList(critical, pseudo);
116 }
117}Python Solution for LeetCode 1489
1class Solution:
2 def findCriticalAndPseudoCriticalEdges(self, n: int, edges: List[List[int]]) -> List[List[int]]:
3 # Add original index to edges: [u, v, w, index]
4 for i, edge in enumerate(edges):
5 edge.append(i)
6
7 # Sort by weight
8 edges.sort(key=lambda x: x[2])
9
10 parent = list(range(n))
11 def find(i):
12 if parent[i] != i:
13 parent[i] = find(parent[i])
14 return parent[i]
15
16 def union(i, j):
17 root_i = find(i)
18 root_j = find(j)
19 if root_i != root_j:
20 parent[root_i] = root_j
21 return True
22 return False
23
24 critical = []
25 pseudo = []
26
27 # Tarjan's helper variables
28 disc = [0] * n
29 low = [0] * n
30 timer = 0
31 is_critical = set()
32
33 def tarjan(u, p_edge_idx, adj):
34 nonlocal timer
35 timer += 1
36 disc[u] = low[u] = timer
37
38 for v, idx in adj[u]:
39 if idx == p_edge_idx:
40 continue
41 if disc[v]:
42 low[u] = min(low[u], disc[v])
43 else:
44 tarjan(v, idx, adj)
45 low[u] = min(low[u], low[v])
46 if low[v] > disc[u]:
47 critical.append(idx)
48 is_critical.add(idx)
49
50 i = 0
51 while i < len(edges):
52 j = i
53 while j < len(edges) and edges[j][2] == edges[i][2]:
54 j += 1
55
56 # Build the graph for this batch
57 # Nodes are the component roots
58 batch_adj = {}
59 unique_nodes = set()
60
61 for k in range(i, j):
62 u, v, w, idx = edges[k]
63 root_u, root_v = find(u), find(v)
64
65 if root_u != root_v:
66 if root_u not in batch_adj: batch_adj[root_u] = []
67 if root_v not in batch_adj: batch_adj[root_v] = []
68 batch_adj[root_u].append((root_v, idx))
69 batch_adj[root_v].append((root_u, idx))
70 unique_nodes.add(root_u)
71 unique_nodes.add(root_v)
72
73 # Run Tarjan's
74 # Reset discovery times for nodes in this batch
75 for node in unique_nodes:
76 disc[node] = 0
77 low[node] = 0
78
79 timer = 0
80 for node in unique_nodes:
81 if disc[node] == 0:
82 tarjan(node, -1, batch_adj)
83
84 # Identify Pseudo-Critical
85 for k in range(i, j):
86 u, v, w, idx = edges[k]
87 root_u, root_v = find(u), find(v)
88 if root_u != root_v and idx not in is_critical:
89 pseudo.append(idx)
90
91 # Union components
92 for k in range(i, j):
93 union(edges[k][0], edges[k][1])
94
95 i = j
96
97 return [critical, pseudo]