Find the minimum number of edges to be removed such that no path exists between the given pair of vertices

Approach

We will solve the above problem greedily by the following approach: 

1. First, sort the input array of vertices in increasing order of the 2nd value of the pairs.
2. We will now maintain a variable minEdge which will maintain the minimum number of edges required to be removed. Initialize minEdge to 0 i.e minEdge = 0.
3. We will also maintain the smallest valued node, reachable from the last node, i.e., N. 
   Initialize reachable = 0.
4. Now traverse the input array of pairs for every pair [u,v]:  
   If (reachable>u), then no path exists between u and v.
5. Remove the edge between v and (v-1). Update reachable = v and increment the minEdge by 1.
6. Output: minEdge

Dry Run

1. Input: 
   N = 9 
   arr[] = [{7,9}, {1,8}, {2,7}, {3,5}, {4,6}]
    
2. After sorting in increasing order of the 2nd value:
   arr[] = [ {3,5}, {4,6}, {2,7}, {1,8}, {7,9} ]
    
3. Initialize minEdge = 0 and reachable = 0.
    
4. Initially, graphs look like this: 
   
5. Now we will traverse the sorted input for every pair (u,v): 
   1. For the pair {3,5}, since reachable = 1 i.e we can reach from the Nth vertex to 1. Since {3,5} lies in between only, we can also reach from vertex 5 to 3 too. Therefore we can remove the last edge between v and (v-1), i.e., remove the edge [4,5].
      Now reachable = v = 5 and minEdge = 1.
       
   2. For the pair {4,6}, since reachable>u (5>4); therefore no path exist between [4,6].
      
      How can we say no path exists between [u,v] if reachable>u?
      Since we have already sorted the array based on the 2nd value, we know reachable will always be less than or equal to the 2nd value, i.e., reachable < v. 
      Therefore if reachable > u, we can reach v from Nth vertex, but we can’t reach u from N. Hence no path exists from v to u.
       
   3. For the pair {2,7}, since reachable>u, therefore again, no path exists between [2,7].
       
   4. For the pair {1,8}, since reachable>u, therefore, again, no path exists between [1,8].
       
   5. For the pair {7,9}, since reachable<u, therefore a path exists between 7 and 9. To remove this path, delete an edge between v and (v-1), i.e., remove the edge [8,9].
      
      Update  reachable = v = 9 and minEdge = 2
       
6. Therefore output will be 2. 

Code in C++

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

bool compare(pair<int,int> p1,pair<int,int> p2){
	return p1.second<p2.second;
}
int findMinEdgesToBeRemoved(vector<pair<int,int> >& arr,int N){
	sort(arr.begin(),arr.end(),compare); 
	int minEdges = 0;
	int reachable = 1;
	for(int i=0;i<arr.size();i++){
		int u = arr[i].first;
		int v = arr[i].second;
		if(reachable>u){
			// no path exist between [u,v];
		}else{
			reachable = v;
			minEdges++;
		}
	}
	return minEdges;
}
int main(){

	int n1 = 9;
	vector<pair<int,int> > arr1{{3, 5}, {7, 9}, {1, 8}, {2, 7}, {4, 6}};
	cout<<findMinEdgesToBeRemoved(arr1,n1)<<endl;

	int n2 = 5;
	vector<pair<int,int> > arr2{{2,5}, {1,4}};
	cout<<findMinEdgesToBeRemoved(arr2,n2)<<endl;
}

You can also try this code with Online C++ Compiler

Run Code

Output

2
1

Time Complexity 

Since we will be sorting the vertices array, the time complexity is O(m*log(m)) where m = number of vertices given as input.

Space Complexity 

Since we are not using any extra space, therefore space complexity is O(1).

Frequently Asked Questions 

1. What is the difference between a tree and a graph?
   Trees and graphs are different since there can never be loops in a tree, but we can have loops in a graph. Also, all the nodes in a tree are always connected, but that is not true for a graph.
    
2. What is the difference between a DFS Traversal and a BFS Traversal?
   In a DFS traversal of a graph, we begin from any random node and travel down each branch as feasible before returning to the current node. In contrast, in a BFS traversal, we visit each node at the current level before visiting their children nodes. 
   DFS Traversal is performed using a stack, whereas a BFS Traversal is performed using a queue.
    
3. Is there anything more in Coding Ninjas Studio that deals with Data Structures and Algorithms?
   Yes, Coding Ninjas Studio offers both coding practice and frequently asked interview questions. The more we practice, the greater our chances of landing a job at our ideal organization.

Key Takeaways

This article taught us how to determine the minimum number of edges that need to be removed from the given graph such that no path exists between the given pair of vertices.

Check out this problem - Pair Sum In Array.

Since graphs are frequently asked in interviews, we recommend you practice more problems based on graphs on Coding Ninjas Studio. 
Are you planning to ace the interviews of reputed product-based companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!