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 function ; Building graph in the form of a adjacency list
#include <bits/stdc++.h> NEW_LINE using namespace std ; set < int > node ; vector < int > Graph [ 10001 ] ; void dfs ( bool visit [ ] , int src ) { visit [ src ] = true ; node . insert ( src ) ; int len = Graph [ src ] . size ( ) ; for ( int i = 0 ; i < len ; i ++ ) if ( ! visit [ Graph [ src ] [ i ] ] ) dfs ( visit , Graph [ src ] [ i ] ) ; } 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 ] . push_back ( q ) ; Graph [ q ] . push_back ( p ) ; } } int compute ( int n ) { bool visit [ n + 5 ] ; memset ( visit , false , sizeof ( visit ) ) ; int number_of_nodes = 0 ; for ( int i = 0 ; i < n ; i ++ ) { if ( ! visit [ i ] ) { node . clear ( ) ; dfs ( visit , i ) ; int count = 0 ; for ( auto it = node . begin ( ) ; it != node . end ( ) ; ++ it ) count += Graph [ ( * it ) ] . size ( ) ; count /= 2 ; if ( count == node . size ( ) - 1 ) number_of_nodes ++ ; } } return number_of_nodes ; } int main ( ) { int n = 6 , m = 4 ; int x [ m + 5 ] = { 1 , 1 , 4 , 4 } ; int y [ m + 5 ] = { 2 , 3 , 5 , 6 } ; buildGraph ( x , y , n ) ; cout << compute ( n ) << " ▁ weakly ▁ connected ▁ nodes " ; return 0 ; }