Weighted union - find with path compression
class wunionfind : NEW_LINE INDENT def __init__ ( self ) : NEW_LINE INDENT self . id = [ 0 for i in range ( 1 , N + 1 ) ] NEW_LINE self . sz = [ 0 for i in range ( 1 , N + 1 ) ] NEW_LINE DEDENT def initial ( self , n ) : NEW_LINE INDENT for i in range ( 1 , n + 1 ) : NEW_LINE INDENT self . id [ i ] = i NEW_LINE self . sz [ i ] = 1 NEW_LINE DEDENT DEDENT def Root ( self , idx ) : NEW_LINE INDENT i = idx ; NEW_LINE while ( i != self . id [ i ] ) : NEW_LINE INDENT self . id [ i ] = self . id [ self . id [ i ] ] NEW_LINE i = self . id [ i ] ; NEW_LINE DEDENT return i ; NEW_LINE DEDENT def Union ( self , a , b ) : NEW_LINE INDENT i = self . Root ( a ) NEW_LINE j = self . Root ( b ) ; NEW_LINE if ( i != j ) : NEW_LINE INDENT if ( self . sz [ i ] >= self . sz [ j ] ) : NEW_LINE INDENT self . id [ j ] = i NEW_LINE self . sz [ i ] += self . sz [ j ] ; NEW_LINE self . sz [ j ] = 0 ; NEW_LINE DEDENT else : NEW_LINE INDENT self . id [ i ] = j NEW_LINE self . sz [ j ] += self . sz [ i ] ; NEW_LINE self . sz [ i ] = 0 NEW_LINE DEDENT DEDENT DEDENT DEDENT W = wunionfind ( ) NEW_LINE