Minimum number of edges required to be removed from an Undirected Graph to make it acyclic | 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 readonly count ; Driver Code
let vec = new Array ( 100001 ) ; let vis = new Array ( 100001 ) ; vis . fill ( false ) ; let cc = 1 ; function dfs ( node ) { vis [ node ] = true ; for ( let x = 0 ; x < vec [ node ] . length ; x ++ ) { if ( ! vis [ vec [ node ] [ x ] ] ) { cc ++ ; dfs ( vec [ node ] [ x ] ) ; } } } function addEdge ( u , v ) { vec [ u ] . push ( v ) ; vec [ v ] . push ( u ) ; } function minEdgeRemoved ( N , M , Edges ) { for ( let i = 0 ; i < M ; i ++ ) { addEdge ( Edges [ i ] [ 0 ] , Edges [ i ] [ 1 ] ) ; } let k = 0 ; for ( let i = 1 ; i <= N ; i ++ ) { if ( ! vis [ i ] ) { cc = 1 ; dfs ( i ) ; k ++ ; } } document . write ( ( M - N + k ) + " " ) ; } let N = 3 , M = 2 ; let Edges = [ [ 1 , 2 ] , [ 2 , 3 ] ] ; for ( let i = 0 ; i < vec . length ; i ++ ) vec [ i ] = [ ] ; minEdgeRemoved ( N , M , Edges ) ;