Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Approach
4.
Dry Run
5.
Code in C++
5.1.
Output
5.2.
Time Complexity 
5.3.
Space Complexity 
6.
Frequently Asked Questions 
7.
Key Takeaways
Last Updated: Mar 27, 2024

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

Author Gaurish Anand
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

Introduction

Before beginning with this question, let’s recap what a graph means.                     

A graph is a non-linear data structure that contains edges that connect vertices.  

Graphs can be either directed or undirected. A directed graph consists of nodes/vertices connected by edges where each edge has a direction. The edges of a graph are represented using arrows pointing in the direction of traversal. If there is an arrow from 1 to 2, the graph can be traversed from 1 to 2 rather than 2 to 1. Whereas in an undirected graph, we can traverse in either direction, i.e., we can travel in the graph from 1 to 2 and 2 to 1 if the graph is undirected.

Problem Statement

We are given a graph with N nodes where we have an edge between the vertex i and the vertex (i+1). You are also given an array of pairs. Your task is to determine the minimum number of edges that need to be deleted from the graph so that each pair (u, v) in the given array has no path. Examples: 

Input: N = 5     array[] = [{2,5}, {1,4}]

Output: 1
Explanation: Remove the edge [3,4]

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

Output: 2
Explanation: Remove the edge [4,5] and [8,9]. 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

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;
}

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!

Previous article
Minimum Vertex Cover Size of a Graph Using Binary Search
Next article
Count the number of nodes in a Graph whose sum of neighbors is at most K
Live masterclass