Dynamic Connectivity | Set 1 ( Incremental ) | Java implementation of incremental connectivity ; Finding the root of node i ; union of two nodes a and b ; union based on rank ; Returns true if two nodes have same root ; Performing an operation according to query type ; type 1 query means checking if node x and y are connected or not ; If roots of x and y is same then yes is the answer ; type 2 query refers union of x and y ; If x and y have different roots then union them ; Driver Code ; No . of nodes ; The following two arrays are used to implement disjoint set data structure . arr [ ] holds the parent nodes while rank array holds the rank of subset ; initializing both array and rank ; number of queries
import java . util . * ; class GFG { static int root ( int arr [ ] , int i ) { while ( arr [ i ] != i ) { arr [ i ] = arr [ arr [ i ] ] ; i = arr [ i ] ; } return i ; } static void weighted_union ( int arr [ ] , int rank [ ] , int a , int b ) { int root_a = root ( arr , a ) ; int root_b = root ( arr , b ) ; if ( rank [ root_a ] < rank [ root_b ] ) { arr [ root_a ] = arr [ root_b ] ; rank [ root_b ] += rank [ root_a ] ; } else { arr [ root_b ] = arr [ root_a ] ; rank [ root_a ] += rank [ root_b ] ; } } static boolean areSame ( int arr [ ] , int a , int b ) { return ( root ( arr , a ) == root ( arr , b ) ) ; } static void query ( int type , int x , int y , int arr [ ] , int rank [ ] ) { if ( type == 1 ) { if ( areSame ( arr , x , y ) == true ) System . out . println ( " Yes " ) ; else System . out . println ( " No " ) ; } else if ( type == 2 ) { if ( areSame ( arr , x , y ) == false ) weighted_union ( arr , rank , x , y ) ; } } public static void main ( String [ ] args ) { int n = 7 ; int [ ] arr = new int [ n ] ; int [ ] rank = new int [ n ] ; for ( int i = 0 ; i < n ; i ++ ) { arr [ i ] = i ; rank [ i ] = 1 ; } int q = 11 ; query ( 1 , 0 , 1 , arr , rank ) ; query ( 2 , 0 , 1 , arr , rank ) ; query ( 2 , 1 , 2 , arr , rank ) ; query ( 1 , 0 , 2 , arr , rank ) ; query ( 2 , 0 , 2 , arr , rank ) ; query ( 2 , 2 , 3 , arr , rank ) ; query ( 2 , 3 , 4 , arr , rank ) ; query ( 1 , 0 , 5 , arr , rank ) ; query ( 2 , 4 , 5 , arr , rank ) ; query ( 2 , 5 , 6 , arr , rank ) ; query ( 1 , 2 , 6 , arr , rank ) ; } }