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 final count ; Driver Code
vec = [ [ ] for i in range ( 100001 ) ] NEW_LINE vis = [ False ] * 100001 NEW_LINE cc = 1 NEW_LINE def dfs ( node ) : NEW_LINE INDENT global cc NEW_LINE vis [ node ] = True NEW_LINE for x in vec [ node ] : NEW_LINE INDENT if ( vis [ x ] == 0 ) : NEW_LINE INDENT cc += 1 NEW_LINE dfs ( x ) NEW_LINE DEDENT DEDENT DEDENT def addEdge ( u , v ) : NEW_LINE INDENT vec [ u ] . append ( v ) NEW_LINE vec [ v ] . append ( u ) NEW_LINE DEDENT def minEdgeRemoved ( N , M , Edges ) : NEW_LINE INDENT global cc NEW_LINE for i in range ( M ) : NEW_LINE INDENT addEdge ( Edges [ i ] [ 0 ] , Edges [ i ] [ 1 ] ) NEW_LINE DEDENT memset ( vis , false , sizeof ( vis ) ) NEW_LINE k = 0 NEW_LINE for i in range ( 1 , N + 1 ) : NEW_LINE INDENT if ( not vis [ i ] ) : NEW_LINE INDENT cc = 1 NEW_LINE dfs ( i ) NEW_LINE k += 1 NEW_LINE DEDENT DEDENT print ( M - N + k ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT N = 3 NEW_LINE M = 2 NEW_LINE Edges = [ [ 1 , 2 ] , [ 2 , 3 ] ] NEW_LINE minEdgeRemoved ( N , M , Edges ) NEW_LINE DEDENT