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: using System ; using System . Collections ; using System . Collections . Generic ; class GFG { static Dictionary < int , int > [ ] g = new Dictionary < int , int > [ 200005 ] ; static HashSet < int > s = new HashSet < int > ( ) ; static HashSet < int > ns = new HashSet < int > ( ) ; static void dfs ( int x ) { ArrayList v = new ArrayList ( ) ; ns . Clear ( ) ; foreach ( int it in s ) { if ( g [ x ] . ContainsKey ( it ) ) { v . Add ( it ) ; } else { ns . Add ( it ) ; } } s = ns ; foreach ( int i in v ) { dfs ( i ) ; } } static void weightOfMST ( int N ) { int cnt = 0 ; for ( int i = 1 ; i <= N ; ++ i ) { s . Add ( i ) ; } ArrayList qt = new ArrayList ( ) ; foreach ( int t in s ) qt . Add ( t ) ; while ( qt . Count != 0 ) { ++ cnt ; int t = ( int ) qt [ 0 ] ; qt . RemoveAt ( 0 ) ; dfs ( t ) ; } Console . Write ( cnt - 4 ) ; } public static void Main ( string [ ] args ) { 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 < 11 ; i ++ ) g [ i ] = new Dictionary < int , int > ( ) ; 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 ) ; } }