Approach
We will solve the above problem greedily by the following approach:
 First, sort the input array of vertices in increasing order of the 2nd value of the pairs.
 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.

We will also maintain the smallest valued node, reachable from the last node, i.e., N.
Initialize reachable = 0.

Now traverse the input array of pairs for every pair [u,v]:
If (reachable>u), then no path exists between u and v.
 Remove the edge between v and (v1). Update reachable = v and increment the minEdge by 1.
 Output: minEdge
Dry Run

Input:
N = 9
arr[] = [{7,9}, {1,8}, {2,7}, {3,5}, {4,6}]

After sorting in increasing order of the 2nd value:
arr[] = [ {3,5}, {4,6}, {2,7}, {1,8}, {7,9} ]

Initialize minEdge = 0 and reachable = 0.

Initially, graphs look like this:

Now we will traverse the sorted input for every pair (u,v):

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 (v1), i.e., remove the edge [4,5].
Now reachable = v = 5 and minEdge = 1.

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.

For the pair {2,7}, since reachable>u, therefore again, no path exists between [2,7].

For the pair {1,8}, since reachable>u, therefore, again, no path exists between [1,8].

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 (v1), i.e., remove the edge [8,9].
Update reachable = v = 9 and minEdge = 2
 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;
}
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

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.

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.

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 productbased companies like Amazon, Google, Microsoft, and more? Attempt our Online Mock Test Series on Coding Ninjas Studio now!