Dynamic Connectivity | Set 1 ( Incremental ) | 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 disjoset data structure . arr [ ] holds the parent nodes while rank array holds the rank of subset ; initializing both array and rank ; number of queries
def root ( arr , i ) : NEW_LINE INDENT while ( arr [ i ] != i ) : NEW_LINE INDENT arr [ i ] = arr [ arr [ i ] ] NEW_LINE i = arr [ i ] NEW_LINE DEDENT return i NEW_LINE DEDENT def weighted_union ( arr , rank , a , b ) : NEW_LINE INDENT root_a = root ( arr , a ) NEW_LINE root_b = root ( arr , b ) NEW_LINE if ( rank [ root_a ] < rank [ root_b ] ) : NEW_LINE INDENT arr [ root_a ] = arr [ root_b ] NEW_LINE rank [ root_b ] += rank [ root_a ] NEW_LINE DEDENT else : NEW_LINE INDENT arr [ root_b ] = arr [ root_a ] NEW_LINE rank [ root_a ] += rank [ root_b ] NEW_LINE DEDENT DEDENT def areSame ( arr , a , b ) : NEW_LINE INDENT return ( root ( arr , a ) == root ( arr , b ) ) NEW_LINE DEDENT def query ( type , x , y , arr , rank ) : NEW_LINE INDENT if ( type == 1 ) : NEW_LINE INDENT if ( areSame ( arr , x , y ) == True ) : NEW_LINE INDENT print ( " Yes " ) NEW_LINE DEDENT else : NEW_LINE INDENT print ( " No " ) NEW_LINE DEDENT DEDENT elif ( type == 2 ) : NEW_LINE INDENT if ( areSame ( arr , x , y ) == False ) : NEW_LINE INDENT weighted_union ( arr , rank , x , y ) NEW_LINE DEDENT DEDENT DEDENT if __name__ == ' _ _ main _ _ ' : NEW_LINE INDENT n = 7 NEW_LINE arr = [ None ] * n NEW_LINE rank = [ None ] * n NEW_LINE for i in range ( n ) : NEW_LINE INDENT arr [ i ] = i NEW_LINE rank [ i ] = 1 NEW_LINE DEDENT q = 11 NEW_LINE query ( 1 , 0 , 1 , arr , rank ) NEW_LINE query ( 2 , 0 , 1 , arr , rank ) NEW_LINE query ( 2 , 1 , 2 , arr , rank ) NEW_LINE query ( 1 , 0 , 2 , arr , rank ) NEW_LINE query ( 2 , 0 , 2 , arr , rank ) NEW_LINE query ( 2 , 2 , 3 , arr , rank ) NEW_LINE query ( 2 , 3 , 4 , arr , rank ) NEW_LINE query ( 1 , 0 , 5 , arr , rank ) NEW_LINE query ( 2 , 4 , 5 , arr , rank ) NEW_LINE query ( 2 , 5 , 6 , arr , rank ) NEW_LINE query ( 1 , 2 , 6 , arr , rank ) NEW_LINE DEDENT