Maximum Nodes removed to Keep the Graph Reachable
You and your Friend are given an undirected graph having 3 types of edges. A graph is called Reachable if starting from any node, you and your friend can reach all other nodes. Print the maximum number of edges that you can remove in order for the graph to remain Reachable. or print -1.
- Type 1: could be traveled by you only
- Type 2: could be traveled by your friend only
- Type 3: could be traveled by both you and your friend
Examples:
Input: graph[type, u, v] = [[3, 1, 2], [3, 2, 3], [1, 1, 3], [1, 2, 4], [1, 1, 2], [2, 3, 4]], n = 4
Output: 2
Explanation: If we remove the two edges [1,1,2] and [1,1,3] Alice and Bob will still be able to traverse the graph. Any additional edge removal, beyond this point will not enable traversal. Hence the maximum number of edges we can remove is two.Input: graph[type, u, v] = [[3, 2, 3], [1, 1, 2], [2, 3, 4]], n = 4
Output: -1
Explanation: In the given graph it is not possible for Alice to reach node 4 from any node and likewise for Bob to reach node 1. Therefore achieving traversal of the graph is impossible.
Approach: To solve the problem follow the below idea:
To solve this problem we utilize the union find data structure. This structure allows us to keep track of components, for each of the three types of edges (1, 2 and 3). Our algorithm proceeds by iterating through the edges in descending order of type. During each iteration we perform union operations. Keep count of the edges. The final result is obtained by subtracting the count of used edges from the number of edges, which represents the removal required to satisfy the disjoint set condition.
To solve the problem follow the below steps:
- Create a helper function called “find” that carries out the find operation within the union find data structure. This function returns the root element of a given elements set.
- Initialize a vector called “ds_both” to represent the disjoint set for type 3 edges. Each element within this vector is initially set to 1 as an indicator for a singleton set.
- Utilize a loop to iterate over all three types of edges (, from type 3 down to type 1).
- Within this loop create a disjoint set called “ds_one” for handling edges of the current type (excluding type 3).
- Iterate through all the edges. Perform union find operations based on their types. Increment our counter for each redundant edge encountered.
- Once you have processed type 3 edges you need to ensure that the graph is fully connected for each person (excluding type 3). If its not simply return 1.
Below is the C++ implementation of above approach:
C++
// C++ code for the above approach: #include <iostream> #include <vector> using namespace std; int find(vector< int >& ds, int i) { return ds[i] < 0 ? i : ds[i] = find(ds, ds[i]); } int maxNumEdgesToRemove( int n, vector<vector< int > >& edges) { vector< int > ds_both(n + 1, -1); int used = 0; for ( int type = 3; type > 0; --type) { auto ds_one = ds_both; auto & ds = type == 3 ? ds_both : ds_one; for ( auto & e : edges) { if (e[0] == type) { int i = find(ds, e[1]), j = find(ds, e[2]); if (i != j) { ++used; if (ds[j] < ds[i]) swap(i, j); ds[i] += ds[j]; ds[j] = i; } } } if (type != 3 && ds[find(ds, 1)] != -n) return -1; } return edges.size() - used; } // Drivers code int main() { int n = 4; vector<vector< int > > edges = { { 3, 1, 2 }, { 3, 2, 3 }, { 1, 1, 3 }, { 1, 2, 4 }, { 1, 1, 2 }, { 2, 3, 4 } }; int result = maxNumEdgesToRemove(n, edges); // Function Call cout << "Result: " << result << endl; return 0; } |
Java
// Java code for the above approach: import java.util.Arrays; class GFG { static int find( int [] ds, int i) { if (ds[i] < 0 ) return i; return ds[i] = find(ds, ds[i]); } static int maxNumEdgesToRemove( int n, int [][] edges) { int [] ds_both = new int [n + 1 ]; Arrays.fill(ds_both, - 1 ); int used = 0 ; for ( int type = 3 ; type > 0 ; --type) { int [] ds_one = ds_both.clone(); int [] ds = type == 3 ? ds_both : ds_one; for ( int [] e : edges) { if (e[ 0 ] == type) { int i = find(ds, e[ 1 ]), j = find(ds, e[ 2 ]); if (i != j) { ++used; if (ds[j] < ds[i]) { int t = i; i = j; j = t; } ds[i] += ds[j]; ds[j] = i; } } } if (type != 3 && ds[find(ds, 1 )] != -n) return - 1 ; } return edges.length - used; } // Drivers code public static void main(String[] args) { int n = 4 ; int [][] edges = { { 3 , 1 , 2 }, { 3 , 2 , 3 }, { 1 , 1 , 3 }, { 1 , 2 , 4 }, { 1 , 1 , 2 }, { 2 , 3 , 4 } }; // Function Call int result = maxNumEdgesToRemove(n, edges); System.out.println( "Result: " + result); } } // This code is contributed by ragul21 |
C#
// C# program for the above approach using System; class GFG { // Function to find the root parent of a node in the // disjoint set static int Find( int [] ds, int i) { if (ds[i] < 0) return i; // Path compression optimization: Set the parent of // each node directly to the root parent return ds[i] = Find(ds, ds[i]); } // Function to determine the maximum number of edges to // remove static int MaxNumEdgesToRemove( int n, int [][] edges) { // Initialize disjoint set data structure for both // Alice and Bob int [] dsBoth = new int [n + 1]; Array.Fill( dsBoth, -1); // Initialize all elements as disjoint sets int used = 0; // Counter to track the number of used // edges // Process each type of edge in reverse order for ( int type = 3; type > 0; --type) { int [] dsOne = ( int [])dsBoth .Clone(); // Clone the disjoint set // for each type of edge int [] ds = type == 3 ? dsBoth : dsOne; // Choose the appropriate // disjoint set // Process each edge foreach ( int [] e in edges) { if (e[0] == type) // Check if the edge type // matches the current // iteration { // Find the root parents of the two // nodes connected by the edge int i = Find(ds, e[1]); int j = Find(ds, e[2]); if (i != j) // If the nodes are in // different sets { ++used; // Increment the count of // used edges if (ds[j] < ds[i]) // Union by rank: // Attach the smaller // tree to the larger // tree { int t = i; i = j; j = t; } ds[i] += ds[j]; // Update the size of // the disjoint set ds[j] = i; // Set the parent of j to i } } } // Check for disjoint set validity for types 1 // and 2 if (type != 3 && ds[Find(ds, 1)] != -n) return -1; // If disjoint set is invalid, // return -1 } // Calculate the remaining unused edges return edges.Length - used; } // Main method public static void Main( string [] args) { int n = 4; // Number of nodes int [][] edges = new int [][] { new int [] { 3, 1, 2 }, new int [] { 3, 2, 3 }, new int [] { 1, 1, 3 }, new int [] { 1, 2, 4 }, new int [] { 1, 1, 2 }, new int [] { 2, 3, 4 } }; // Edge list with format [type, node1, node2] // Function Call int result = MaxNumEdgesToRemove(n, edges); Console.WriteLine( "Result: " + result); } } // This code is contributed by Susobhan Akhuli |
Javascript
// Function to find the parent of the set containing element i function find(ds, i) { // If ds[i] is negative, it means i is the parent itself if (ds[i] < 0) return i; // Otherwise, recursively find the parent of i return ds[i] = find(ds, ds[i]); } // Function to determine the maximum number of edges that can be removed function maxNumEdgesToRemove(n, edges) { // Initialize disjoint sets array for both types of edges let ds_both = new Array(n + 1).fill(-1); // Initialize the count of used edges to 0 let used = 0; // Loop through each type of edge (type 3, type 2, type 1) for (let type = 3; type > 0; --type) { // Clone the disjoint sets array based on the current type let ds_one = [...ds_both]; let ds = type === 3 ? ds_both : ds_one; // Iterate through each edge for (let e of edges) { // Check if the edge type matches the current type if (e[0] === type) { // Find the parents of the vertices connected by this edge let i = find(ds, e[1]), j = find(ds, e[2]); // If the vertices are in different sets, merge them if (i !== j) { ++used; // Increment the count of used edges // Union by size: merge the smaller set into the larger one if (ds[j] < ds[i]) { let t = i; i = j; j = t; } ds[i] += ds[j]; ds[j] = i; } } } // If the current type is not type 3 and the first vertex doesn't belong to a set of size -n, return -1 if (type !== 3 && ds[find(ds, 1)] !== -n) return -1; } // Return the total number of edges minus the used edges return edges.length - used; } // Driver code let n = 4; let edges = [ [3, 1, 2], [3, 2, 3], [1, 1, 3], [1, 2, 4], [1, 1, 2], [2, 3, 4] ]; // Function call to find the maximum number of edges that can be removed let result = maxNumEdgesToRemove(n, edges); console.log( "Result: " + result); // Output the result |
Python3
# Python program for the above approach def find(ds, i): # Find operation in disjoint-set data structure return i if ds[i] < 0 else find(ds, ds[i]) def max_num_edges_to_remove(n, edges): # Initialize disjoint-set data structures ds_both = [ - 1 ] * (n + 1 ) used = 0 # Counter for the number of used edges # Iterate over the three types of edges in reverse order for type in range ( 3 , 0 , - 1 ): ds_one = list (ds_both) ds = ds_both if type = = 3 else ds_one # Process edges of the current type for e in edges: if e[ 0 ] = = type : i, j = find(ds, e[ 1 ]), find(ds, e[ 2 ]) if i ! = j: # If the nodes are not in the same set, union them used + = 1 if ds[j] < ds[i]: i, j = j, i ds[i] + = ds[j] ds[j] = i # Check for disjoint-set validity for types 1 and 2 if type ! = 3 and ds[find(ds, 1 )] ! = - n: return - 1 # Calculate the remaining unused edges return len (edges) - used # Driver code n = 4 edges = [[ 3 , 1 , 2 ], [ 3 , 2 , 3 ], [ 1 , 1 , 3 ], [ 1 , 2 , 4 ], [ 1 , 1 , 2 ], [ 2 , 3 , 4 ]] result = max_num_edges_to_remove(n, edges) # Output the result print ( "Result:" , result) # This code is contributed by Susobhan Akhuli |
Result: 2
Time Complexity: O(E * α(V))Where E is the number of edges (E), and the inverse Ackermann function (α) and V is the number of nodes (V). It can be considered constant.
Auxiliary Space: O(V) where is the number of nodes (V).
Contact Us