Minimum labelled node to be removed from undirected Graph such that there is no cycle | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int MAX = 100005 ; int totBackEdges ; int countAdj [ MAX ] , small [ MAX ] ; int isPossible [ MAX ] , depth [ MAX ] ; vector < int > adj [ MAX ] ; int vis [ MAX ] ; void change ( pair < int , int > & p , int x ) { if ( p . second > x ) p . second = x ; if ( p . first > p . second ) swap ( p . first , p . second ) ; } pair < int , int > dfs ( int v , int p = -1 , int de = 0 ) { pair < int , int > answer ( 100000000 , 100000000 ) ; depth [ v ] = de ; vis [ v ] = 1 ; isPossible [ v ] = 1 ; for ( int u : adj [ v ] ) { if ( u ^ p ) { if ( ! vis [ u ] ) { auto 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 ; } int minNodetoRemove ( int n , vector < pair < int , int > > edges ) { for ( int i = 0 ; i < edges . size ( ) ; i ++ ) { adj [ edges [ i ] . first ] . push_back ( edges [ i ] . second ) ; adj [ edges [ i ] . second ] . push_back ( edges [ i ] . first ) ; } memset ( vis , 0 , sizeof ( vis ) ) ; totBackEdges = 0 ; for ( int v = 1 ; v <= n ; v ++ ) { if ( ! vis [ v ] ) dfs ( v ) ; } if ( totBackEdges == 0 ) return -1 ; int node = -1 ; for ( int v = 1 ; v <= n ; v ++ ) { if ( countAdj [ v ] + small [ v ] == totBackEdges && isPossible [ v ] ) { node = v ; } if ( node != -1 ) break ; } return node ; } int main ( ) { int N = 5 ; vector < pair < int , int > > edges ; edges . push_back ( make_pair ( 5 , 1 ) ) ; edges . push_back ( make_pair ( 5 , 2 ) ) ; edges . push_back ( make_pair ( 1 , 2 ) ) ; edges . push_back ( make_pair ( 2 , 3 ) ) ; edges . push_back ( make_pair ( 2 , 4 ) ) ; cout << minNodetoRemove ( N , edges ) ; }