Minimum cost required to connect all houses in a city | Python3 program for the above approach ; Utility function to find set of an element v using path compression technique ; If v is the parent ; Otherwise , recursively find its parent ; Function to perform union of the sets a and b ; Find parent of a and b ; If parent are different ; Swap Operation ; Update parent of b as a ; Otherwise , return 0 ; Function to create a Minimum Cost Spanning tree for given houses ; Stores adjacency list of graph ; Traverse each coordinate ; Find the Manhattan distance ; Add the edges ; Sort all the edges ; Initialize parent [ ] and size [ ] ; Stores the minimum cost ; Finding the minimum cost ; Perform the unioun operation ; Print the minimum cost ; Driver Code ; Given houses ; Function Call
parent = [ 0 ] * 100 NEW_LINE size = [ 0 ] * 100 NEW_LINE def find_set ( v ) : NEW_LINE INDENT if ( v == parent [ v ] ) : NEW_LINE INDENT return v NEW_LINE DEDENT parent [ v ] = find_set ( parent [ v ] ) NEW_LINE return parent [ v ] NEW_LINE DEDENT def union_sets ( a , b ) : NEW_LINE INDENT a = find_set ( a ) NEW_LINE b = find_set ( b ) NEW_LINE if ( a != b ) : NEW_LINE INDENT if ( size [ a ] < size [ b ] ) : NEW_LINE INDENT a , b = b , a NEW_LINE DEDENT parent [ b ] = a NEW_LINE size [ a ] += size [ b ] NEW_LINE return 1 NEW_LINE DEDENT return 0 NEW_LINE DEDENT def MST ( houses , n ) : NEW_LINE INDENT v = [ ] NEW_LINE for i in range ( n ) : NEW_LINE INDENT for j in range ( i + 1 , n ) : NEW_LINE INDENT p = abs ( houses [ i ] [ 0 ] - houses [ j ] [ 0 ] ) NEW_LINE p += abs ( houses [ i ] [ 1 ] - houses [ j ] [ 1 ] ) NEW_LINE v . append ( [ p , i , j ] ) NEW_LINE DEDENT DEDENT v = sorted ( v ) NEW_LINE for i in range ( n ) : NEW_LINE INDENT parent [ i ] = i NEW_LINE size [ i ] = 1 NEW_LINE DEDENT ans = 0 NEW_LINE for x in v : NEW_LINE INDENT if ( union_sets ( x [ 1 ] , x [ 2 ] ) ) : NEW_LINE INDENT ans += x [ 0 ] NEW_LINE DEDENT DEDENT print ( ans ) NEW_LINE DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT houses = [ [ 0 , 0 ] , [ 2 , 2 ] , [ 3 , 10 ] , [ 5 , 2 ] , [ 7 , 0 ] ] NEW_LINE N = len ( houses ) NEW_LINE MST ( houses , N ) NEW_LINE DEDENT