text: Find weight of MST in a complete graph with edge | C ++ Program to find weight of minimum spanning tree in a complete graph where edges have weight either 0 or 1 ; To store the edges of the given graph ; A utility function to perform DFS Traversal ; Check those vertices which are stored in the set ; Vertices are included if the weight of edge is 0 ; A utility function to find the weight of Minimum Spanning Tree ; To count the connected components ; Inserting the initial vertices in the set ; Traversing vertices stored in the set and Run DFS Traversal for each vertices ; Incrementing the zero weight connected components ; DFS Traversal for every vertex remove ; Driver 's Code ; Insert edges ; Function call find the weight of Minimum Spanning Tree
code: #include <bits/stdc++.h> NEW_LINE using namespace std ; map < int , int > g [ 200005 ] ; set < int > s , ns ; void dfs ( int x ) { vector < int > v ; v . clear ( ) ; ns . clear ( ) ; for ( int it : s ) { if ( ! g [ x ] [ it ] ) { v . push_back ( it ) ; } else { ns . insert ( it ) ; } } s = ns ; for ( int i : v ) { dfs ( i ) ; } } void weightOfMST ( int N ) { int cnt = 0 ; for ( int i = 1 ; i <= N ; ++ i ) { s . insert ( i ) ; } for ( ; s . size ( ) ; ) { ++ cnt ; int t = * s . begin ( ) ; s . erase ( t ) ; dfs ( t ) ; } cout << cnt - 1 ; } int main ( ) { int N = 6 , M = 11 ; int edges [ ] [ ] = { { 1 , 3 } , { 1 , 4 } , { 1 , 5 } , { 1 , 6 } , { 2 , 3 } , { 2 , 4 } , { 2 , 5 } , { 2 , 6 } , { 3 , 4 } , { 3 , 5 } , { 3 , 6 } } ; for ( int i = 0 ; i < M ; ++ i ) { int u = edges [ i ] [ 0 ] ; int v = edges [ i ] [ 1 ] ; g [ u ] [ v ] = 1 ; g [ v ] [ u ] = 1 ; } weightOfMST ( N ) ; return 0 ; }