Weighted union - find with path compression
struct wunionfind { int id [ N ] , sz [ N ] ; void initial ( int n ) { for ( int i = 1 ; i <= n ; i ++ ) id [ i ] = i , sz [ i ] = 1 ; } int Root ( int idx ) { int i = idx ; while ( i != id [ i ] ) id [ i ] = id [ id [ i ] ] , i = id [ i ] ; return i ; } void Union ( int a , int b ) { int i = Root ( a ) , j = Root ( b ) ; if ( i != j ) { if ( sz [ i ] >= sz [ j ] ) { id [ j ] = i , sz [ i ] += sz [ j ] ; sz [ j ] = 0 ; } else { id [ i ] = j , sz [ j ] += sz [ i ] ; sz [ i ] = 0 ; } } } } ; wunionfind W ;