Minimum number of edges required to be removed from an Undirected Graph to make it acyclic | C ++ Program to implement the above approach ; Stores the adjacency list ; Stores if a vertex is visited or not ; Function to perform DFS Traversal to count the number and size of all connected components ; Mark the current node as visited ; Traverse the adjacency list of the current node ; For every unvisited node ; Recursive DFS Call ; Function to add undirected edge in the graph ; Function to calculate minimum number of edges to be removed ; Create Adjacency list ; Iterate over all the nodes ; Print the final count ; Driver Code
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > vec [ 100001 ] ; bool vis [ 100001 ] ; int cc = 1 ; void dfs ( int node ) { vis [ node ] = true ; for ( auto x : vec [ node ] ) { if ( ! vis [ x ] ) { cc ++ ; dfs ( x ) ; } } } void addEdge ( int u , int v ) { vec [ u ] . push_back ( v ) ; vec [ v ] . push_back ( u ) ; } void minEdgeRemoved ( int N , int M , int Edges [ ] [ 2 ] ) { for ( int i = 0 ; i < M ; i ++ ) { addEdge ( Edges [ i ] [ 0 ] , Edges [ i ] [ 1 ] ) ; } memset ( vis , false , sizeof ( vis ) ) ; int k = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { if ( ! vis [ i ] ) { cc = 1 ; dfs ( i ) ; k ++ ; } } cout << M - N + k << endl ; } int main ( ) { int N = 3 , M = 2 ; int Edges [ ] [ 2 ] = { { 1 , 2 } , { 2 , 3 } } ; minEdgeRemoved ( N , M , Edges ) ; }