Given two integers N and M denoting the number of vertices and edges in the graph and array edges[][] of size M, denoting an edge between edges[i][0] and edges[i][1], the task is to find the minimum edges directly connected with node B that must be removed such that there exist no path between vertex A and B.
Examples:
Input: N = 4, A = 3, B = 2, edges[][] = {{3, 1}, {3, 4}, {1, 2}, {4, 2}}
Output: 2
Explanation: The edges at index 2 and 3 i.e., {1, 2} and {4, 2} must be removed as they both are in the path from vertex A to vertex B.Input: N = 6, A = 1, B = 6, edges[][] = {{1, 2}, {1, 6}, {2, 6}, {1, 4}, {4, 6}, {4, 3}, {2, 4}}
Output: 3
Approach: The given problem can be solved using a Depth-first search algorithm. It can be observed that all the edges associated with the ending vertex B and exist in any path from starting node A and ending at node B must be removed. Hence, perform a dfs starting from node A and maintain all the visited vertices from it. Follow the steps below to solve the problem:
- Create an adjacency matrix g[][] which stores the edges between two nodes.
- Initialize an array v[], to mark the node which can be reached from node A.
- Create a variable cnt, which stores the count of nodes needed to be removed. Initially, cnt = 0.
- Iterate through all the nodes and if it is reachable from A and is directly connected with B, increment the value of cnt.
- The value stored in cnt is the required answer.
Below is the implementation of the above approach:
C++
// C++ program for the above approach#include <bits/stdc++.h>using namespace std;// Function for Depth first Searchvoid dfs(int s, vector<vector<int> > g, vector<int>& v){ for (auto i : g[s]) { // If current vertex is // not visited yet if (!v[i]) { v[i] = 1; // Recursive call for // dfs function dfs(i, g, v); } }}// Function to find the out the minimum// number of edges that must be removedint deleteEdges(int n, int m, int a, int b, vector<vector<int> > edges){ // Creating Adjacency Matrix vector<vector<int> > g(n, vector<int>()); for (int i = 0; i < m; i++) { g[edges[i][0] - 1].push_back(edges[i][1] - 1); g[edges[i][1] - 1].push_back(edges[i][0] - 1); } // Vector for marking visited vector<int> v(n, 0); v[a - 1] = 1; // Calling dfs function dfs(a - 1, g, v); // Stores the final count int cnt = 0; for (int i = 0; i < n; i++) { // If current node can not // be visited from node A if (v[i] == 0) continue; for (int j = 0; j < g[i].size(); j++) { // If a node between current // node and node b exist if (g[i][j] == b - 1) { cnt++; } } } // Return Answer return cnt;}// Driver Codeint main(){ int N = 6; int M = 7; int A = 1; int B = 6; vector<vector<int> > edges{ { 1, 2 }, { 5, 2 }, { 2, 4 }, { 2, 3 }, { 3, 6 }, { 4, 6 }, { 5, 6 } }; cout << deleteEdges(N, M, A, B, edges); return 0;} |
Java
// Java program for the above approachimport java.util.*;class GFG{// Function for Depth first Searchstatic void dfs(int s, Vector<Integer> [] g, int[] v){ for (int i : g[s]) { // If current vertex is // not visited yet if (v[i] == 0) { v[i] = 1; // Recursive call for // dfs function dfs(i, g, v); } }}// Function to find the out the minimum// number of edges that must be removedstatic int deleteEdges(int n, int m, int a, int b, int[][] edges){ // Creating Adjacency Matrix Vector<Integer> []g = new Vector[n]; for (int i = 0; i < g.length; i++) g[i] = new Vector<Integer>(); for (int i = 0; i < m; i++) { g[edges[i][0] - 1].add(edges[i][1] - 1); g[edges[i][1] - 1].add(edges[i][0] - 1); } // Vector for marking visited int []v = new int[n]; v[a - 1] = 1; // Calling dfs function dfs(a - 1, g, v); // Stores the final count int cnt = 0; for (int i = 0; i < n; i++) { // If current node can not // be visited from node A if (v[i] == 0) continue; for (int j = 0; j < g[i].size(); j++) { // If a node between current // node and node b exist if (g[i].get(j) == b - 1) { cnt++; } } } // Return Answer return cnt;}// Driver Codepublic static void main(String[] args){ int N = 6; int M = 7; int A = 1; int B = 6; int[][] edges ={ { 1, 2 }, { 5, 2 }, { 2, 4 }, { 2, 3 }, { 3, 6 }, { 4, 6 }, { 5, 6 } }; System.out.print(deleteEdges(N, M, A, B, edges));}}// This code is contributed by 29AjayKumar |
Python3
# Python program for the above approach# Function for Depth first Searchdef dfs(s, g, v): for i in g[s]: # If current vertex is # not visited yet if not v[i]: v[i] = 1 # Recursive call for # dfs function dfs(i, g, v)# Function to find the out the minimum# number of edges that must be removeddef deleteEdges(n, m, a, b, edges): # Creating Adjacency Matrix g = [0] * m for i in range(len(g)): g[i] = [] for i in range(m): g[edges[i][0] - 1].append(edges[i][1] - 1) g[edges[i][1] - 1].append(edges[i][0] - 1) # Vector for marking visited v = [0] * n v[a - 1] = 1 # Calling dfs function dfs(a - 1, g, v) # Stores the final count cnt = 0 for i in range(n): # If current node can not # be visited from node A if (v[i] == 0): continue for j in range(len(g[i])): # If a node between current # node and node b exist if (g[i][j] == b - 1): cnt += 1 # Return Answer return cnt# Driver CodeN = 6M = 7A = 1B = 6edges = [[1, 2], [5, 2], [2, 4], [2, 3], [3, 6], [4, 6], [5, 6]]print(deleteEdges(N, M, A, B, edges))# This code is contributed by gfgking |
C#
// C# program for the above approachusing System;using System.Collections.Generic;public class GFG{// Function for Depth first Searchstatic void dfs(int s, List<int> [] g, int[] v){ foreach (int i in g[s]) { // If current vertex is // not visited yet if (v[i] == 0) { v[i] = 1; // Recursive call for // dfs function dfs(i, g, v); } }}// Function to find the out the minimum// number of edges that must be removedstatic int deleteEdges(int n, int m, int a, int b, int[,] edges){ // Creating Adjacency Matrix List<int> []g = new List<int>[n]; for (int i = 0; i < g.Length; i++) g[i] = new List<int>(); for (int i = 0; i < m; i++) { g[edges[i,0] - 1].Add(edges[i,1] - 1); g[edges[i,1] - 1].Add(edges[i,0] - 1); } // List for marking visited int []v = new int[n]; v[a - 1] = 1; // Calling dfs function dfs(a - 1, g, v); // Stores the readonly count int cnt = 0; for (int i = 0; i < n; i++) { // If current node can not // be visited from node A if (v[i] == 0) continue; for (int j = 0; j < g[i].Count; j++) { // If a node between current // node and node b exist if (g[i][j] == b - 1) { cnt++; } } } // Return Answer return cnt;}// Driver Codepublic static void Main(String[] args){ int N = 6; int M = 7; int A = 1; int B = 6; int[,] edges ={ { 1, 2 }, { 5, 2 }, { 2, 4 }, { 2, 3 }, { 3, 6 }, { 4, 6 }, { 5, 6 } }; Console.Write(deleteEdges(N, M, A, B, edges));}}// This code is contributed by shikhasingrajput |
Javascript
<script>// JavaScript program for the above approach// Function for Depth first Searchfunction dfs(s, g, v){ for(let i of g[s]) { // If current vertex is // not visited yet if (!v[i]) { v[i] = 1; // Recursive call for // dfs function dfs(i, g, v); } }}// Function to find the out the minimum// number of edges that must be removedfunction deleteEdges(n, m, a, b, edges) { // Creating Adjacency Matrix let g = new Array(m); for(let i = 0; i < g.length; i++) { g[i] = []; } for(let i = 0; i < m; i++) { g[edges[i][0] - 1].push(edges[i][1] - 1); g[edges[i][1] - 1].push(edges[i][0] - 1); } // Vector for marking visited let v = new Array(n).fill(0) v[a - 1] = 1; // Calling dfs function dfs(a - 1, g, v); // Stores the final count let cnt = 0; for(let i = 0; i < n; i++) { // If current node can not // be visited from node A if (v[i] == 0) continue; for(let j = 0; j < g[i].length; j++) { // If a node between current // node and node b exist if (g[i][j] == b - 1) { cnt++; } } } // Return Answer return cnt;}// Driver Codelet N = 6;let M = 7;let A = 1;let B = 6;let edges = [ [ 1, 2 ], [ 5, 2 ], [ 2, 4 ], [ 2, 3 ], [ 3, 6 ], [ 4, 6 ], [ 5, 6 ] ];document.write(deleteEdges(N, M, A, B, edges));// This code is contributed by Potta Lokesh</script> |
Output
3
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
