Number of Critical and Pseudo-Critical edges
Given a weighted undirected graph with n vertices numbered from 0 to n – 1, and an array of edges where edges[i] = [u, v, weight] represents a bidirectional and weighted edge between nodes u and v. Find all the critical and pseudo-critical edges in the given graph’s MST.
An MST edge whose deletoin 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.
Examples:
Input: Vertices: 5
Edges: [u v weight]=[[0 1 1],[1 2 1],[2 3 2],[0 3 2],[0 4 3],[3 4 3],[1 4 6]]
Output: critical : [0,1], psedo critical : [2 3 4 5]
Explanation:
The two edges 0 and 1 appear in all MSTs, therefore they are critical edges
The edges 2, 3, 4, and 5 are only part of some MSTs, therefore they are considered pseudo-critical edges.
Input: Vertices = 4, Edges: [u v weight]= [[0,1,1],[1,2,1],[2,3,1],[0,3,1]]
Output: critcal : [ ] pseudo critical: [0 1 2 3]
Explanation: It’s noticeable that when all four edges possess equal weight, selecting any three edges out of the provided four will result in a minimum spanning tree (MST). As a consequence, all four edges can be classified as pseudo-critical and there is no critical edges
Approach:
This problem can be solved using a variation of Union Find Algorithm to store the edges and then use Kruskal’s algorithm to find the MST.
- Create a new array to store the edges and corresponding indices.
- Sort the edges array.
- Then find the Weight of Actual MST.
- Then, find the Critical and Pseudo Critical Edges
Below is the implementation of the above approach (the explanation of the code is given at the end of this implementation):
C++
#include <bits/stdc++.h> using namespace std; vector< int > parent; // Initialize the disjoint-set data structure void disjoint( int size) { parent.resize(size + 1); for ( int i = 0; i <= size; i++) // Each element is initially its own parent parent[i] = i; } // Finding the representative of the // disjoint-set containing 'u' int find( int u) { // If 'u' is its own parent, it's the // representative. if (parent[u] == u) return u; // Path compression. return parent[u] = find(parent[u]); } // Merge two disjoint-sets // represented by 'u' and 'v' void merge( int u, int v) { int ua = find(u); int ub = find(v); // Set the representative of 'u' as the // representative of 'v'. parent[ua] = ub; } // function to find the minimum // spanning tree (MST) weight int help1(vector<vector< int > >& e, int j, int n) { disjoint(n + 1); vector<pair< int , pair< int , int > > > v; for ( int i = 0; i < e.size(); i++) { if (i == j) continue ; // Add edge weight and // vertices to 'v'. v.push_back({ e[i][2], { e[i][0], e[i][1] } }); } // Sort edges by weight. sort(v.begin(), v.end()); int mst_weight = 0; int edges = 0; for ( int i = 0; i < v.size(); i++) { auto x = v[i]; int u = find(x.second.first); int v = find(x.second.second); if (u != v) { // Add edge weight to MST. edges++; mst_weight += x.first; // Merge the disjoint-sets // of 'u' and 'v'. merge(u, v); } } // If not all vertices // are included in MST. if (edges != n - 1) return INT_MAX; return mst_weight; } // function to find MST weight after // including one additional edge int help2(vector<vector< int > >& e, int j, int n) { disjoint(n + 1); // Include the current edge in MST. int mst_weight = e[j][2]; // Merge vertices of the current edge. merge(e[j][1], e[j][0]); vector<pair< int , pair< int , int > > > v; for ( int i = 0; i < e.size(); i++) { if (i == j) continue ; // Add edge weight and // vertices to 'v'. v.push_back({ e[i][2], { e[i][0], e[i][1] } }); } // Sort edges by weight. sort(v.begin(), v.end()); for ( int i = 0; i < v.size(); i++) { auto x = v[i]; int u = find(x.second.first); int v = find(x.second.second); if (u != v) { // Add edge weight to MST. mst_weight += x.first; // Merge the disjoint-sets of 'u' // and 'v'. merge(u, v); } } return mst_weight; } // Function to determine whether the edge // is Critical or Pseudi-Critical vector<vector< int > > findCriticalAndPseudoCriticalEdges( int n, vector<vector< int > >& e) { disjoint(n + 1); // Compute MST weight without any excluded edge. int mst_weight = help1(e, -1, n); // Store critical edges in v1 and // pseudo-critical edges in v2. vector< int > v1, v2; // combine v1 and v2 to return // as a 2d vector vector<vector< int > > ans; for ( int i = 0; i < e.size(); i++) { // MST weight without the i-th edge. int new_weight1 = help1(e, i, n); // MST weight with the i-th edge. int new_weight2 = help2(e, i, n); // i-th edge is critical. if (new_weight1 > mst_weight) { v1.push_back(i); } // i-th edge is pseudo-critical. else if (new_weight2 == mst_weight) { v2.push_back(i); } } // Critical edges. ans.push_back(v1); // Pseudo-critical edges. ans.push_back(v2); return ans; } // Driver code int main() { int vertices = 5; vector<vector< int > > ans; vector<vector< int > > edges; edges.push_back({ 0, 1, 1 }); edges.push_back({ 1, 2, 1 }); edges.push_back({ 2, 3, 2 }); edges.push_back({ 0, 3, 2 }); edges.push_back({ 0, 4, 3 }); edges.push_back({ 3, 4, 3 }); edges.push_back({ 1, 4, 6 }); ans = findCriticalAndPseudoCriticalEdges(vertices, edges); // Printing the ans for ( auto it : ans) { cout << "["; for ( auto i : it) { cout << i << " "; } cout << "]"; cout << endl; } return 0; } |
Java
// Java code for the above approach import java.util.ArrayList; import java.util.Collections; import java.util.List; class GFG { static List<Integer> parent; // Initialize the disjoint-set data structure static void disjoint( int size) { parent = new ArrayList<>(size + 1 ); for ( int i = 0 ; i <= size; i++) { // Each element is initially its own parent parent.add(i); } } // Finding the representative of the // disjoint-set containing 'u' static int find( int u) { // If 'u' is its own parent, it's the // representative. if (parent.get(u) == u) return u; // Path compression. parent.set(u, find(parent.get(u))); return parent.get(u); } // Merge two disjoint-sets // represented by 'u' and 'v' static void merge( int u, int v) { int ua = find(u); int ub = find(v); // Set the representative of 'u' as the // representative of 'v'. parent.set(ua, ub); } // function to find the minimum // spanning tree (MST) weight static int help1(List< int []> e, int j, int n) { disjoint(n + 1 ); List<Pair<Integer, Pair<Integer, Integer> > > v = new ArrayList<>(); for ( int i = 0 ; i < e.size(); i++) { if (i == j) continue ; // Add edge weight and // vertices to 'v'. v.add( new Pair<>( e.get(i)[ 2 ], new Pair<>(e.get(i)[ 0 ], e.get(i)[ 1 ]))); } // Sort edges by weight. Collections.sort(v, (a, b) -> a.getKey() - b.getKey()); int mst_weight = 0 ; int edges = 0 ; for ( int i = 0 ; i < v.size(); i++) { Pair<Integer, Pair<Integer, Integer> > x = v.get(i); int a = find(x.getValue().getKey()); int b = find(x.getValue().getValue()); if (a != b) { // Add edge weight to MST. edges++; mst_weight += x.getKey(); // Merge the disjoint-sets // of 'u' and 'v'. merge(a, b); } } // If not all vertices // are included in MST. if (edges != n - 1 ) return Integer.MAX_VALUE; return mst_weight; } // function to find MST weight after // including one additional edge static int help2(List< int []> e, int j, int n) { disjoint(n + 1 ); // Include the current edge in MST. int mst_weight = e.get(j)[ 2 ]; // Merge vertices of the current edge. merge(e.get(j)[ 1 ], e.get(j)[ 0 ]); List<Pair<Integer, Pair<Integer, Integer> > > v = new ArrayList<>(); for ( int i = 0 ; i < e.size(); i++) { if (i == j) continue ; // Add edge weight and // vertices to 'v'. v.add( new Pair<>( e.get(i)[ 2 ], new Pair<>(e.get(i)[ 0 ], e.get(i)[ 1 ]))); } // Sort edges by weight. Collections.sort(v, (a, b) -> a.getKey() - b.getKey()); for ( int i = 0 ; i < v.size(); i++) { Pair<Integer, Pair<Integer, Integer> > x = v.get(i); int a = find(x.getValue().getKey()); int b = find(x.getValue().getValue()); if (a != b) { // Add edge weight to MST. mst_weight += x.getKey(); // Merge the disjoint-sets of 'u' // and 'v'. merge(a, b); } } return mst_weight; } // Function to determine whether the edge // is Critical or Pseudo-Critical static List<List<Integer> > findCriticalAndPseudoCriticalEdges( int n, List< int []> e) { disjoint(n + 1 ); // Compute MST weight without any excluded edge. int mst_weight = help1(e, - 1 , n); // Store critical edges in v1 and // pseudo-critical edges in v2. List<Integer> v1 = new ArrayList<>(); List<Integer> v2 = new ArrayList<>(); // Combine v1 and v2 to return // as a 2D list List<List<Integer> > ans = new ArrayList<>(); for ( int i = 0 ; i < e.size(); i++) { // MST weight without the i-th edge. int new_weight1 = help1(e, i, n); // MST weight with the i-th edge. int new_weight2 = help2(e, i, n); // i-th edge is critical. if (new_weight1 > mst_weight) { v1.add(i); } // i-th edge is pseudo-critical. else if (new_weight2 == mst_weight) { v2.add(i); } } // Critical edges. ans.add(v1); // Pseudo-critical edges. ans.add(v2); return ans; } // Driver code public static void main(String[] args) { int vertices = 5 ; List<List<Integer> > ans; List< int []> edges = new ArrayList<>(); edges.add( new int [] { 0 , 1 , 1 }); edges.add( new int [] { 1 , 2 , 1 }); edges.add( new int [] { 2 , 3 , 2 }); edges.add( new int [] { 0 , 3 , 2 }); edges.add( new int [] { 0 , 4 , 3 }); edges.add( new int [] { 3 , 4 , 3 }); edges.add( new int [] { 1 , 4 , 6 }); ans = findCriticalAndPseudoCriticalEdges(vertices, edges); // Printing the ans for (List<Integer> it : ans) { System.out.print( "[" ); for ( int i : it) { System.out.print(i + " " ); } System.out.println( "]" ); } } static class Pair<K, V> { private final K key; private final V value; public Pair(K key, V value) { this .key = key; this .value = value; } public K getKey() { return key; } public V getValue() { return value; } } } // This code is contributed by ragul21 |
Python3
from collections import defaultdict parent = [] # Initialize the disjoint-set data structure def disjoint(size): global parent parent = list ( range (size + 1 )) # Finding the representative of the disjoint-set containing 'u' def find(u): # If 'u' is its own parent, it's the representative. if parent[u] = = u: return u # Path compression. parent[u] = find(parent[u]) return parent[u] # Merge two disjoint-sets represented by 'u' and 'v' def merge(u, v): ua = find(u) ub = find(v) # Set the representative of 'u' as the representative of 'v'. parent[ua] = ub # Function to find the minimum spanning tree (MST) weight def help1(e, j, n): disjoint(n + 1 ) edges = [] for i in range ( len (e)): if i = = j: continue # Add edge weight and vertices to 'edges'. edges.append((e[i][ 2 ], (e[i][ 0 ], e[i][ 1 ]))) # Sort edges by weight. edges.sort() mst_weight = 0 edges_count = 0 for i in range ( len (edges)): edge = edges[i] u = find(edge[ 1 ][ 0 ]) v = find(edge[ 1 ][ 1 ]) if u ! = v: # Add edge weight to MST. edges_count + = 1 mst_weight + = edge[ 0 ] # Merge the disjoint-sets of 'u' and 'v'. merge(u, v) # If not all vertices are included in MST. if edges_count ! = n - 1 : return float ( 'inf' ) return mst_weight # Function to find MST weight after including one additional edge def help2(e, j, n): disjoint(n + 1 ) # Include the current edge in MST. mst_weight = e[j][ 2 ] # Merge vertices of the current edge. merge(e[j][ 1 ], e[j][ 0 ]) edges = [] for i in range ( len (e)): if i = = j: continue # Add edge weight and vertices to 'edges'. edges.append((e[i][ 2 ], (e[i][ 0 ], e[i][ 1 ]))) # Sort edges by weight. edges.sort() for i in range ( len (edges)): edge = edges[i] u = find(edge[ 1 ][ 0 ]) v = find(edge[ 1 ][ 1 ]) if u ! = v: # Add edge weight to MST. mst_weight + = edge[ 0 ] # Merge the disjoint-sets of 'u' and 'v'. merge(u, v) return mst_weight # Function to determine whether the edge is Critical or Pseudo-Critical def findCriticalAndPseudoCriticalEdges(n, e): disjoint(n + 1 ) # Compute MST weight without any excluded edge. mst_weight = help1(e, - 1 , n) # Store critical edges in v1 and pseudo-critical edges in v2. v1, v2 = [], [] for i in range ( len (e)): # MST weight without the i-th edge. new_weight1 = help1(e, i, n) # MST weight with the i-th edge. new_weight2 = help2(e, i, n) # i-th edge is critical. if new_weight1 > mst_weight: v1.append(i) # i-th edge is pseudo-critical. elif new_weight2 = = mst_weight: v2.append(i) # Critical edges and Pseudo-critical edges. return [v1, v2] # Driver code if __name__ = = "__main__" : vertices = 5 edges = [ [ 0 , 1 , 1 ], [ 1 , 2 , 1 ], [ 2 , 3 , 2 ], [ 0 , 3 , 2 ], [ 0 , 4 , 3 ], [ 3 , 4 , 3 ], [ 1 , 4 , 6 ] ] ans = findCriticalAndPseudoCriticalEdges(vertices, edges) # Printing the ans for it in ans: print ( "[" , end = "") for i in it: print (i, end = " " ) print ( "]" ) # This code is contributed by shivamgupta0987654321 |
C#
using System; using System.Collections.Generic; using System.Linq; class CriticalEdges { static List< int > parent; // Initialize the disjoint-set data structure static void Disjoint( int size) { parent = new List< int >(size + 1); for ( int i = 0; i <= size; i++) { // Each element is initially its own parent parent.Add(i); } } // Finding the representative of the // disjoint-set containing 'u' static int Find( int u) { // If 'u' is its own parent, it's the // representative. if (parent[u] == u) return u; // Path compression. return parent[u] = Find(parent[u]); } // Merge two disjoint-sets // represented by 'u' and 'v' static void Merge( int u, int v) { int ua = Find(u); int ub = Find(v); // Set the representative of 'u' as the // representative of 'v'. parent[ua] = ub; } // function to find the minimum // spanning tree (MST) weight static int Help1(List<List< int >> e, int j, int n) { Disjoint(n + 1); List<Tuple< int , Tuple< int , int >>> v = new List<Tuple< int , Tuple< int , int >>>(); for ( int i = 0; i < e.Count; i++) { if (i == j) continue ; // Add edge weight and // vertices to 'v'. v.Add( new Tuple< int , Tuple< int , int >>(e[i][2], new Tuple< int , int >(e[i][0], e[i][1]))); } // Sort edges by weight. v = v.OrderBy(x => x.Item1).ToList(); int mstWeight = 0; int edges = 0; foreach ( var x in v) { int u = Find(x.Item2.Item1); int vrtx = Find(x.Item2.Item2); if (u != vrtx) { // Add edge weight to MST. edges++; mstWeight += x.Item1; // Merge the disjoint-sets // of 'u' and 'v'. Merge(u, vrtx); } } // If not all vertices // are included in MST. if (edges != n - 1) return int .MaxValue; return mstWeight; } // function to find MST weight after // including one additional edge static int Help2(List<List< int >> e, int j, int n) { Disjoint(n + 1); // Include the current edge in MST. int mstWeight = e[j][2]; // Merge vertices of the current edge. Merge(e[j][1], e[j][0]); List<Tuple< int , Tuple< int , int >>> v = new List<Tuple< int , Tuple< int , int >>>(); for ( int i = 0; i < e.Count; i++) { if (i == j) continue ; // Add edge weight and // vertices to 'v'. v.Add( new Tuple< int , Tuple< int , int >>(e[i][2], new Tuple< int , int >(e[i][0], e[i][1]))); } // Sort edges by weight. v = v.OrderBy(x => x.Item1).ToList(); foreach ( var x in v) { int u = Find(x.Item2.Item1); int vrtx = Find(x.Item2.Item2); if (u != vrtx) { // Add edge weight to MST. mstWeight += x.Item1; // Merge the disjoint-sets of 'u' // and 'v'. Merge(u, vrtx); } } return mstWeight; } // Function to determine whether the edge // is Critical or Pseudi-Critical static List<List< int >> FindCriticalAndPseudoCriticalEdges( int n, List<List< int >> e) { Disjoint(n + 1); // Compute MST weight without any excluded edge. int mstWeight = Help1(e, -1, n); // Store critical edges in v1 and // pseudo-critical edges in v2. List< int > v1 = new List< int >(); List< int > v2 = new List< int >(); // combine v1 and v2 to return // as a 2d vector List<List< int >> ans = new List<List< int >>(); for ( int i = 0; i < e.Count; i++) { // MST weight without the i-th edge. int newWeight1 = Help1(e, i, n); // MST weight with the i-th edge. int newWeight2 = Help2(e, i, n); // i-th edge is critical. if (newWeight1 > mstWeight) { v1.Add(i); } // i-th edge is pseudo-critical. else if (newWeight2 == mstWeight) { v2.Add(i); } } // Critical edges. ans.Add(v1); // Pseudo-critical edges. ans.Add(v2); return ans; } // Driver code public static void Main( string [] args) { int vertices = 5; List<List< int >> ans; List<List< int >> edges = new List<List< int >>() { new List< int > { 0, 1, 1 }, new List< int > { 1, 2, 1 }, new List< int > { 2, 3, 2 }, new List< int > { 0, 3, 2 }, new List< int > { 0, 4, 3 }, new List< int > { 3, 4, 3 }, new List< int > { 1, 4, 6 } }; ans = FindCriticalAndPseudoCriticalEdges(vertices, edges); // Printing the ans foreach ( var it in ans) { Console.Write( "[" ); foreach ( var i in it) { Console.Write(i + " " ); } Console.Write( "]" ); Console.WriteLine(); } } } |
Javascript
// Javascript program for the above approach class Pair { constructor(key, value) { this .key = key; this .value = value; } } let parent; // Initialize the disjoint-set data structure function disjoint(size) { parent = new Array(size + 1); for (let i = 0; i <= size; i++) { // Each element is initially its own parent parent[i] = i; } } // Finding the representative of the disjoint-set containing 'u' function find(u) { // If 'u' is its own parent, it's the representative. if (parent[u] === u) return u; // Path compression. parent[u] = find(parent[u]); return parent[u]; } // Merge two disjoint-sets represented by 'u' and 'v' function merge(u, v) { const ua = find(u); const ub = find(v); // Set the representative of 'u' as the representative of 'v'. parent[ua] = ub; } // function to find the minimum spanning tree (MST) weight function help1(e, j, n) { disjoint(n + 1); const v = []; for (let i = 0; i < e.length; i++) { if (i === j) continue ; // Add edge weight and vertices to 'v'. v.push( new Pair( e[i][2], new Pair(e[i][0], e[i][1]) )); } // Sort edges by weight. v.sort((a, b) => a.key - b.key); let mstWeight = 0; let edges = 0; for (let i = 0; i < v.length; i++) { const x = v[i]; const a = find(x.value.key); const b = find(x.value.value); if (a !== b) { // Add edge weight to MST. edges++; mstWeight += x.key; // Merge the disjoint-sets of 'u' and 'v'. merge(a, b); } } // If not all vertices are included in MST. if (edges !== n - 1) return Infinity; return mstWeight; } // function to find MST weight after including one additional edge function help2(e, j, n) { disjoint(n + 1); // Include the current edge in MST. let mstWeight = e[j][2]; // Merge vertices of the current edge. merge(e[j][1], e[j][0]); const v = []; for (let i = 0; i < e.length; i++) { if (i === j) continue ; // Add edge weight and vertices to 'v'. v.push( new Pair( e[i][2], new Pair(e[i][0], e[i][1]) )); } // Sort edges by weight. v.sort((a, b) => a.key - b.key); for (let i = 0; i < v.length; i++) { const x = v[i]; const a = find(x.value.key); const b = find(x.value.value); if (a !== b) { // Add edge weight to MST. mstWeight += x.key; // Merge the disjoint-sets of 'u' and 'v'. merge(a, b); } } return mstWeight; } // Function to determine whether the edge is Critical or Pseudo-Critical function findCriticalAndPseudoCriticalEdges(n, e) { disjoint(n + 1); // Compute MST weight without any excluded edge. const mstWeight = help1(e, -1, n); // Store critical edges in v1 and pseudo-critical edges in v2. const v1 = []; const v2 = []; for (let i = 0; i < e.length; i++) { // MST weight without the i-th edge. const newWeight1 = help1(e, i, n); // MST weight with the i-th edge. const newWeight2 = help2(e, i, n); // i-th edge is critical. if (newWeight1 > mstWeight) { v1.push(i); } // i-th edge is pseudo-critical. else if (newWeight2 === mstWeight) { v2.push(i); } } // Critical edges. const ans = [v1]; // Pseudo-critical edges. ans.push(v2); return ans; } // Driver code const vertices = 5; const edges = [ [0, 1, 1], [1, 2, 1], [2, 3, 2], [0, 3, 2], [0, 4, 3], [3, 4, 3], [1, 4, 6] ]; // Find Critical and Pseudo-Critical Edges const ans = findCriticalAndPseudoCriticalEdges(vertices, edges); // Printing the ans for (const it of ans) { console.log( "[" + it.join( " " ) + "]" ); } // This code is contributed by Susobhan Akhuli |
[0 1 ] [2 3 4 5 ]
Below is the code explanation to solve the problem:
- The disjoint() function initializes a disjoint-set data structure for a given size. It creates a parent array where each element initially points to itself, indicating that every vertex is in its own disjoint set.
- The find() function is to find the operation of the disjoint-set data structure. It finds the root (parent) of the set to which vertex u belongs. It uses path compression to optimize future find operations.
- The merge() function merges two disjoint sets represented by vertices u and v. It does this by making the parent of one set point to the parent of the other set.
- help1() function computes the MST weight of the graph when edge j is excluded. It uses Kruskal’s algorithm to construct the MST while excluding edge j. It returns the weight of the resulting MST.
- help2() function computes the MST weight of the graph when only edge j is included. It starts with edge j as part of the MST and then continues to add edges using Kruskal’s algorithm. It returns the weight of the resulting MST.
- findCriticalAndPseudoCriticalEdges(int n, vector<vector<int>>& e) function that finds critical and pseudo-critical edges.
- It iterates through all edges in the graph and, for each edge, calculates two MST weights: one when the edge is excluded (new_weight1) and one when only that edge is included (new_weight2).
- Based on these weights, it determines whether the edge is critical or pseudo-critical and adds it to the corresponding lists v1 or v2.
- Finally, it returns these lists in the ans vector.
Time complexity: O(E * log(V)) where E is the number of edges and V is the number of vertices.
Auxiliary Space Complexity: O(E+V) where E is the number of edges and V is the number of vertices.
Contact Us