Minimum number of edges required to be removed from an Undirected Graph to make it acyclic | C # program to implement the above approach ; 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
using System ; using System . Collections . Generic ; class GFG { static List < int > [ ] vec = new List < int > [ 100001 ] ; static bool [ ] vis = new bool [ 100001 ] ; static int cc = 1 ; static void dfs ( int node ) { vis [ node ] = true ; foreach ( int x in vec [ node ] ) { if ( ! vis [ x ] ) { cc ++ ; dfs ( x ) ; } } } static void addEdge ( int u , int v ) { vec [ u ] . Add ( v ) ; vec [ v ] . Add ( u ) ; } static void minEdgeRemoved ( int N , int M , int [ , ] Edges ) { for ( int i = 0 ; i < M ; i ++ ) { addEdge ( Edges [ i , 0 ] , Edges [ i , 1 ] ) ; } int k = 0 ; for ( int i = 1 ; i <= N ; i ++ ) { if ( ! vis [ i ] ) { cc = 1 ; dfs ( i ) ; k ++ ; } } Console . Write ( M - N + k + " STRNEWLINE " ) ; } public static void Main ( String [ ] args ) { int N = 3 , M = 2 ; int [ , ] Edges = { { 1 , 2 } , { 2 , 3 } } ; for ( int i = 0 ; i < vec . Length ; i ++ ) vec [ i ] = new List < int > ( ) ; minEdgeRemoved ( N , M , Edges ) ; } }