Number of connected components of a graph ( using Disjoint Set Union ) | C # program for the above approach ; Stores the parent of each vertex ; Function to find the topmost parent of vertex a ; If current vertex is the topmost vertex ; Otherwise , set topmost vertex of its parent as its topmost vertex ; Function to connect the component having vertex a with the component having vertex b ; Connect edges ; Function to find unique top most parents ; Traverse all vertices ; Insert all topmost vertices obtained ; Print count of connected components ; Function to print answer ; Setting parent to itself ; Traverse all edges ; Print answer ; Driver code ; Given N ; Given edges ; Function call
using System ; using System . Collections . Generic ; class GFG { static int [ ] parent = new int [ 1000000 ] ; static int root ( int a ) { if ( a == parent [ a ] ) { return a ; } return parent [ a ] = root ( parent [ a ] ) ; } static void connect ( int a , int b ) { a = root ( a ) ; b = root ( b ) ; if ( a != b ) { parent [ b ] = a ; } } static void connectedComponents ( int n ) { HashSet < int > s = new HashSet < int > ( ) ; for ( int i = 0 ; i < n ; i ++ ) { s . Add ( parent [ i ] ) ; } Console . WriteLine ( s . Count ) ; } static void printAnswer ( int N , List < List < int > > edges ) { for ( int i = 0 ; i <= N ; i ++ ) { parent [ i ] = i ; } for ( int i = 0 ; i < edges . Count ; i ++ ) { connect ( edges [ i ] [ 0 ] , edges [ i ] [ 1 ] ) ; } connectedComponents ( N ) ; } static void Main ( ) { int N = 8 ; List < List < int > > edges = new List < List < int > > ( ) ; edges . Add ( new List < int > { 1 , 0 } ) ; edges . Add ( new List < int > { 0 , 2 } ) ; edges . Add ( new List < int > { 5 , 3 } ) ; edges . Add ( new List < int > { 3 , 4 } ) ; edges . Add ( new List < int > { 6 , 7 } ) ; printAnswer ( N , edges ) ; } }