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
node = set ( ) NEW_LINE Graph = [ [ ] for i in range ( 10001 ) ] NEW_LINE def dfs ( visit , src ) : NEW_LINE INDENT visit [ src ] = True NEW_LINE node . add ( src ) NEW_LINE llen = len ( Graph [ src ] ) NEW_LINE for i in range ( llen ) : NEW_LINE INDENT if ( not visit [ Graph [ src ] [ i ] ] ) : NEW_LINE INDENT dfs ( visit , Graph [ src ] [ i ] ) NEW_LINE DEDENT DEDENT DEDENT def buildGraph ( x , y , llen ) : NEW_LINE INDENT for i in range ( llen ) : NEW_LINE INDENT p = x [ i ] NEW_LINE q = y [ i ] NEW_LINE Graph [ p ] . append ( q ) NEW_LINE Graph [ q ] . append ( p ) NEW_LINE DEDENT DEDENT def compute ( n ) : NEW_LINE INDENT visit = [ False for i in range ( n + 5 ) ] NEW_LINE number_of_nodes = 0 NEW_LINE for i in range ( n ) : NEW_LINE INDENT if ( not visit [ i ] ) : NEW_LINE INDENT node . clear ( ) NEW_LINE dfs ( visit , i ) NEW_LINE count = 0 NEW_LINE for it in node : NEW_LINE INDENT count += len ( Graph [ ( it ) ] ) NEW_LINE DEDENT count //= 2 NEW_LINE if ( count == len ( node ) - 1 ) : NEW_LINE number_of_nodes += 1 NEW_LINE DEDENT DEDENT return number_of_nodes NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 6 NEW_LINE m = 4 NEW_LINE x = [ 1 , 1 , 4 , 4 , 0 , 0 , 0 , 0 , 0 ] NEW_LINE y = [ 2 , 3 , 5 , 6 , 0 , 0 , 0 , 0 , 0 ] NEW_LINE buildGraph ( x , y , n ) NEW_LINE print ( str ( compute ( n ) ) + " ▁ weakly ▁ connected ▁ nodes " ) NEW_LINE DEDENT