Minimum labelled node to be removed from undirected Graph such that there is no cycle | Java 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
import java . util . ArrayList ; import java . util . Arrays ; class Pair { int first , second ; public Pair ( int first , int second ) { this . first = first ; this . second = second ; } } class GFG { static final int MAX = 100005 ; static int totBackEdges ; static int [ ] countAdj = new int [ MAX ] ; static int [ ] small = new int [ MAX ] ; static int [ ] isPossible = new int [ MAX ] ; static int [ ] depth = new int [ MAX ] ; @ SuppressWarnings ( " unchecked " ) static ArrayList < Integer > [ ] adj = new ArrayList [ MAX ] ; static int [ ] vis = new int [ MAX ] ; static void change ( Pair p , int x ) { if ( p . second > x ) p . second = x ; if ( p . first > p . second ) { int tmp = p . first ; p . first = p . second ; p . second = tmp ; } } static Pair dfs ( int v , int p , int de ) { Pair answer = new Pair ( 100000000 , 100000000 ) ; depth [ v ] = de ; vis [ v ] = 1 ; isPossible [ v ] = 1 ; for ( int u : adj [ v ] ) { if ( ( u ^ p ) != 0 ) { if ( vis [ u ] == 0 ) { Pair 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 ; } static int minNodetoRemove ( int n , ArrayList < Pair > edges ) { for ( int i = 0 ; i < edges . size ( ) ; i ++ ) { adj [ edges . get ( i ) . first ] . add ( edges . get ( i ) . second ) ; adj [ edges . get ( i ) . second ] . add ( edges . get ( i ) . first ) ; } Arrays . fill ( vis , 0 ) ; totBackEdges = 0 ; for ( int v = 1 ; v <= n ; v ++ ) { if ( vis [ v ] == 0 ) dfs ( v , - 1 , 0 ) ; } if ( totBackEdges == 0 ) return - 1 ; int node = - 1 ; for ( int v = 1 ; v <= n ; v ++ ) { if ( ( countAdj [ v ] + small [ v ] == totBackEdges ) && isPossible [ v ] != 0 ) { node = v ; } if ( node != - 1 ) break ; } return node ; } public static void main ( String [ ] args ) { int N = 5 ; ArrayList < Pair > edges = new ArrayList < > ( ) ; for ( int i = 0 ; i < MAX ; i ++ ) { adj [ i ] = new ArrayList < > ( ) ; } edges . add ( new Pair ( 5 , 1 ) ) ; edges . add ( new Pair ( 5 , 2 ) ) ; edges . add ( new Pair ( 1 , 2 ) ) ; edges . add ( new Pair ( 2 , 3 ) ) ; edges . add ( new Pair ( 2 , 4 ) ) ; System . out . println ( minNodetoRemove ( N , edges ) ) ; } }