Minimize the number of weakly connected nodes | C # code to minimize the number of weakly connected nodes ; Set of nodes which are traversed in each launch of the DFS ; Function traversing the graph using DFS approach and updating the set of nodes ; Building a undirected graph ; Computes the minimum number of disconnected components when a bi - directed graph is converted to a undirected graph ; Declaring and initializing a visited array ; We check if each node is visited once or not ; We only launch DFS from a node iff it is unvisited . ; Clearing the set of nodes on every relaunch of DFS ; Relaunching DFS from an unvisited node . ; Iterating over the node set to count the number of nodes visited after making the graph directed and storing it in the variable count . If count / 2 == number of nodes - 1 , then increment count by 1. ; Driver Code ; Building graph in the form of a adjacency list
using System ; using System . Collections ; using System . Collections . Generic ; class GFG { static HashSet < int > node = new HashSet < int > ( ) ; static List < int > [ ] Graph = new List < int > [ 10001 ] ; static void dfs ( bool [ ] visit , int src ) { visit [ src ] = true ; node . Add ( src ) ; int len = Graph [ src ] . Count ; for ( int i = 0 ; i < len ; i ++ ) if ( ! visit [ Graph [ src ] [ i ] ] ) dfs ( visit , Graph [ src ] [ i ] ) ; } static void buildGraph ( int [ ] x , int [ ] y , int len ) { for ( int i = 0 ; i < len ; i ++ ) { int p = x [ i ] ; int q = y [ i ] ; Graph [ p ] . Add ( q ) ; Graph [ q ] . Add ( p ) ; } } static int compute ( int n ) { bool [ ] visit = new bool [ n + 5 ] ; Array . Fill ( visit , false ) ; int number_of_nodes = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( ! visit [ i ] ) { node . Clear ( ) ; dfs ( visit , i ) ; int count = 0 ; foreach ( int it in node ) count += Graph [ ( it ) ] . Count ; count /= 2 ; if ( count == node . Count - 1 ) number_of_nodes ++ ; } } return number_of_nodes ; } static void Main ( string [ ] args ) { int n = 6 ; for ( int i = 0 ; i < 10001 ; i ++ ) { Graph [ i ] = new List < int > ( ) ; } int [ ] x = { 1 , 1 , 4 , 4 , 0 , 0 , 0 , 0 } ; int [ ] y = { 2 , 3 , 5 , 6 , 0 , 0 , 0 , 0 } ; buildGraph ( x , y , n ) ; Console . Write ( compute ( n ) + " ▁ weakly ▁ connected ▁ nodes " ) ; } }