Minimum cost required to connect all houses in a city | C ++ 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; vector < int > parent , size ; int find_set ( int v ) { if ( v == parent [ v ] ) return v ; return parent [ v ] = find_set ( parent [ v ] ) ; } int union_sets ( int a , int b ) { a = find_set ( a ) ; b = find_set ( b ) ; if ( a != b ) { if ( size [ a ] < size [ b ] ) swap ( a , b ) ; parent [ b ] = a ; size [ a ] += size [ b ] ; return 1 ; } return 0 ; } void MST ( int houses [ ] [ 2 ] , int n ) { vector < pair < int , pair < int , int > > > v ; for ( int i = 0 ; i < n ; i ++ ) { for ( int j = i + 1 ; j < n ; j ++ ) { int p = abs ( houses [ i ] [ 0 ] - houses [ j ] [ 0 ] ) ; p += abs ( houses [ i ] [ 1 ] - houses [ j ] [ 1 ] ) ; v . push_back ( { p , { i , j } } ) ; } } parent . resize ( n ) ; size . resize ( n ) ; sort ( v . begin ( ) , v . end ( ) ) ; for ( int i = 0 ; i < n ; i ++ ) { parent [ i ] = i , size [ i ] = 1 ; } int ans = 0 ; for ( auto x : v ) { if ( union_sets ( x . second . first , x . second . second ) ) { ans += x . first ; } } cout << ans ; } int main ( ) { int houses [ ] [ 2 ] = { { 0 , 0 } , { 2 , 2 } , { 3 , 10 } , { 5 , 2 } , { 7 , 0 } } ; int N = sizeof ( houses ) / sizeof ( houses [ 0 ] ) ; MST ( houses , N ) ; return 0 ; }