Water Connection Problem | number of houses and number of pipes ; Array rd stores the ending vertex of pipe ; Array wd stores the value of diameters between two pipes ; Array cd stores the starting end of pipe ; List a , b , c are used to store the final output ; Function performing calculations . ; If a pipe has no ending vertex but has starting vertex i . e is an outgoing pipe then we need to start DFS with this vertex . ; We put the details of component in final output array ; main function ; set the value of the araray to zero
n = 0 NEW_LINE p = 0 NEW_LINE rd = [ 0 ] * 1100 NEW_LINE wt = [ 0 ] * 1100 NEW_LINE cd = [ 0 ] * 1100 NEW_LINE a = [ ] NEW_LINE b = [ ] NEW_LINE c = [ ] NEW_LINE ans = 0 NEW_LINE def dfs ( w ) : NEW_LINE INDENT global ans NEW_LINE if ( cd [ w ] == 0 ) : NEW_LINE INDENT return w NEW_LINE DEDENT if ( wt [ w ] < ans ) : NEW_LINE INDENT ans = wt [ w ] NEW_LINE DEDENT return dfs ( cd [ w ] ) NEW_LINE DEDENT def solve ( arr ) : NEW_LINE INDENT global ans NEW_LINE i = 0 NEW_LINE while ( i < p ) : NEW_LINE INDENT q = arr [ i ] [ 0 ] NEW_LINE h = arr [ i ] [ 1 ] NEW_LINE t = arr [ i ] [ 2 ] NEW_LINE cd [ q ] = h NEW_LINE wt [ q ] = t NEW_LINE rd [ h ] = q NEW_LINE i += 1 NEW_LINE DEDENT a = [ ] NEW_LINE b = [ ] NEW_LINE c = [ ] NEW_LINE for j in range ( 1 , n + 1 ) : NEW_LINE INDENT if ( rd [ j ] == 0 and cd [ j ] ) : NEW_LINE INDENT ans = 1000000000 NEW_LINE w = dfs ( j ) NEW_LINE a . append ( j ) NEW_LINE b . append ( w ) NEW_LINE c . append ( ans ) NEW_LINE DEDENT DEDENT print ( len ( a ) ) NEW_LINE for j in range ( len ( a ) ) : NEW_LINE INDENT print ( a [ j ] , b [ j ] , c [ j ] ) NEW_LINE DEDENT DEDENT n = 9 NEW_LINE p = 6 NEW_LINE arr = [ [ 7 , 4 , 98 ] , [ 5 , 9 , 72 ] , [ 4 , 6 , 10 ] , [ 2 , 8 , 22 ] , [ 9 , 7 , 17 ] , [ 3 , 1 , 66 ] ] NEW_LINE solve ( arr ) NEW_LINE