Grokking Graph Algorithms for Coding Interviews
Ask Author
Back to course home

0% completed

Vote For New Content
Find Critical and Pseudo-Critical Edges in Minimum Spanning Tree (hard)
Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Problem Statement

Given a weighted undirected graph with n vertices numbered from 0 to n-1, and an array edges where edges[i] = [a, b, weight] represents a bidirectional and weighted edge between nodes a and b.

A minimum spanning tree (MST) is a subset of the graph's edges that connects all vertices without cycles and with the smallest possible total edge weight.

An edge is critical if removing it would cause the MST's total weight to increase. An edge is pseudo-critical if it can be part of some MSTs but is not required in all MSTs.

Return a 2D array containing all the critical and pseudo-critical edges in the graph's MST.

Examples

Example 1

  • Input: n = 4, edges = [[0, 1, 1], [1, 2, 2], [2, 3, 3], [0, 3, 4], [1, 3, 5]]
  • Expected Output: [[0,1,2],[]]
Image
  • Justification: Edges [0, 1, 2] are critical as their removal increases the MST weight.

Example 2

  • Input: n = 4, edges = [[0, 1, 1], [1, 2, 1], [2, 3, 1], [0, 3, 1], [0, 2, 2]]
  • Expected Output: [[],[0,1,2,3]]
Image
  • Justification: Edges [0, 1, 2, 3] are pseudo-critical as they exists in some of MSTs.

Example 3

  • Input: n = 6, edges = [[0, 1, 2], [1, 2, 3], [2, 3, 1], [3, 4, 4], [4, 5, 5], [0, 5, 6], [1, 4, 2]]
  • Expected Output: [[0,1,2,4,6],[]]
  • Justification: Edges [0,1,2,4,6] are critical as their removal increases the MST weight.

Constraints:

  • 2 <= n <= 100
  • 1 <= edges.length <= min(200, n * (n - 1) / 2)
  • edges[i].length == 3
  • 0 <= a<sub>i</sub> < b<sub>i</sub> < n
  • 1 <= weight<sub>i</sub> <= 1000
  • All pairs (a<sub>i</sub>, b<sub>i</sub>) are distinct.

Try it yourself

Try solving this question here:

Python3
Python3
. . . .

.....

.....

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible

Contents are not accessible