Minimum labelled node to be removed from undirected Graph such that there is no cycle | Javascript implementation to find the minimum labelled node to be removed such that there is no cycle in the undirected graph ; Variables to store if a node V has at - most one back edge and store the depth of the node for the edge ; Function to swap the pairs of the graph ; If the second value is greater than x ; Put the pair in the ascending order internally ; Function to perform the DFS ; Initialise with the large value ; Storing the depth of this vertex ; Mark the vertex as visited ; Iterating through the graph ; If the node is a child node ; If the child node is unvisited ; Move to the child and increase the depth ; Increase according to algorithm ; If the node is not having exactly K backedges ; If the child is already visited and in current dfs ( because colour is 1 ) then this is a back edge ; Increase the countAdj values ; Colour this vertex 2 as we are exiting out of dfs for this node ; Function to find the minimum labelled node to be removed such that there is no cycle in the undirected graph ; Construct the graph ; Mark visited as false for each node ; Apply dfs on all unmarked nodes ; If no backedges in the initial graph this means that there is no cycle So , return - 1 ; Iterate through the vertices and return the first node that satisfies the condition ; Check whether the count sum of small [ v ] and count is the same as the total back edges and if the vertex v can be removed ; Driver code
var MAX = 100005 ; var totBackEdges ; var countAdj = Array ( MAX ) . fill ( 0 ) ; var small = Array ( MAX ) . fill ( 0 ) ; var isPossible = Array ( MAX ) . fill ( 0 ) ; var depth = Array ( MAX ) . fill ( 0 ) ; var adj = [ ] ; var vis = Array ( MAX ) . fill ( 0 ) ; class pair { constructor ( first , second ) { this . first = first ; this . second = second ; } } function change ( p , x ) { if ( p . second > x ) p . second = x ; if ( p . first > p . second ) { var tmp = p . first ; p . first = p . second ; p . second = tmp ; } } function dfs ( v , p = - 1 , de = 0 ) { var answer = new pair ( 100000000 , 100000000 ) ; depth [ v ] = de ; vis [ v ] = 1 ; isPossible [ v ] = 1 ; for ( var u of adj [ v ] ) { if ( ( u ^ p ) != 0 ) { if ( vis [ u ] == 0 ) { var x = dfs ( u , v , de + 1 ) ; small [ v ] += small [ u ] ; change ( answer , x . second ) ; change ( answer , x . first ) ; if ( x . second < de ) isPossible [ v ] = 0 ; } else if ( vis [ u ] == 1 ) { totBackEdges ++ ; countAdj [ v ] ++ ; countAdj [ u ] ++ ; small [ p ] ++ ; small [ u ] -- ; change ( answer , depth [ u ] ) ; } } } vis [ v ] = 2 ; return answer ; } function minNodetoRemove ( n , edges ) { for ( var i = 0 ; i < edges . length ; i ++ ) { ( adj [ ( edges [ i ] ) . first ] ) . push ( ( edges [ i ] ) . second ) ; ( adj [ ( edges [ i ] ) . second ] ) . push ( ( edges [ i ] ) . first ) ; } vis = Array ( MAX ) . fill ( 0 ) ; totBackEdges = 0 ; for ( var v = 1 ; v <= n ; v ++ ) { if ( vis [ v ] == 0 ) dfs ( v ) ; } if ( totBackEdges == 0 ) return - 1 ; var node = - 1 ; for ( var v = 1 ; v <= n ; v ++ ) { if ( ( countAdj [ v ] + small [ v ] == totBackEdges ) && isPossible [ v ] != 0 ) { node = v ; } if ( node != - 1 ) break ; } return node ; } var N = 5 ; var edges = [ ] ; for ( var i = 0 ; i < MAX ; i ++ ) { adj . push ( new Array ( ) ) ; } edges . push ( new pair ( 5 , 1 ) ) ; edges . push ( new pair ( 5 , 2 ) ) ; edges . push ( new pair ( 1 , 2 ) ) ; edges . push ( new pair ( 2 , 3 ) ) ; edges . push ( new pair ( 2 , 4 ) ) ; document . write ( minNodetoRemove ( N , edges ) ) ;