human
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"
How can the above be solved in Python?
assistant
#Here is code to dynamic Connectivity and the other steps required.
 def root ( arr , i ) :
	while ( arr [ i ] != i ) :
		arr [ i ] = arr [ arr [ i ] ]
		i = arr [ i ]
	return i
def weighted_union ( arr , rank , a , b ) :
	root_a = root ( arr , a )
	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 ]
def areSame ( arr , a , b ) :
	return ( root ( arr , a ) == root ( arr , b ) )
def query ( type , x , y , arr , rank ) :
	if ( type == 1 ) :
		if ( areSame ( arr , x , y ) == True ) :
			print ( " Yes " )
		else :
			print ( " No " )
	elif ( type == 2 ) :
		if ( areSame ( arr , x , y ) == False ) :
			weighted_union ( arr , rank , x , y )
if __name__ == ' _ _ main _ _ ' :
	n = 7
	arr = [ None ] * n
	rank = [ None ] * n
	for i in range ( n ) :
		arr [ i ] = i
		rank [ i ] = 1
	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 )