Find the number of Islands | Set 2 ( Using Disjoint Set ) | Class to represent Disjoint Set Data structure ; Initially , all elements are in their own set . ; Finds the representative of the set that x is an element of ; if x is not the parent of itself , then x is not the representative of its set . so we recursively call Find on its parent and move i 's node directly under the  representative of this set ; Unites the set that includes x and the set that includes y ; Find the representatives ( or the root nodes ) for x an y ; Elements are in the same set , no need to unite anything . ; If x ' s ▁ rank ▁ is ▁ less ▁ than ▁ y ' s rank Then move x under y so that depth of tree remains less ; Else if y ' s ▁ rank ▁ is ▁ less ▁ than ▁ x ' s rank Then move y under x so that depth of tree remains less ; Else if their ranks are the same ; Then move y under x ( doesn 't matter which one goes where) ; And increment the result tree 's  rank by 1 ; Returns number of islands in a [ ] [ ] ; The following loop checks for its neighbours and unites the indexes if both are 1. ; If cell is 0 , nothing to do ; Check all 8 neighbours and do a Union with neighbour 's set if neighbour is  also 1 ; Array to note down frequency of each set ; If frequency of set is 0 , increment numberOfIslands ; Driver Code
class DisjointUnionSets : NEW_LINE INDENT def __init__ ( self , n ) : NEW_LINE INDENT self . rank = [ 0 ] * n NEW_LINE self . parent = [ 0 ] * n NEW_LINE self . n = n NEW_LINE self . makeSet ( ) NEW_LINE DEDENT def makeSet ( self ) : NEW_LINE INDENT for i in range ( self . n ) : NEW_LINE INDENT self . parent [ i ] = i NEW_LINE DEDENT DEDENT def find ( self , x ) : NEW_LINE INDENT if ( self . parent [ x ] != x ) : NEW_LINE INDENT return self . find ( self . parent [ x ] ) NEW_LINE DEDENT return x NEW_LINE DEDENT def Union ( self , x , y ) : NEW_LINE INDENT xRoot = self . find ( x ) NEW_LINE yRoot = self . find ( y ) NEW_LINE if xRoot == yRoot : NEW_LINE INDENT return NEW_LINE DEDENT if self . rank [ xRoot ] < self . rank [ yRoot ] : NEW_LINE INDENT parent [ xRoot ] = yRoot NEW_LINE DEDENT elif self . rank [ yRoot ] < self . rank [ xRoot ] : NEW_LINE INDENT self . parent [ yRoot ] = xRoot NEW_LINE DEDENT else : NEW_LINE INDENT self . parent [ yRoot ] = xRoot NEW_LINE self . rank [ xRoot ] = self . rank [ xRoot ] + 1 NEW_LINE DEDENT DEDENT DEDENT def countIslands ( a ) : NEW_LINE INDENT n = len ( a ) NEW_LINE m = len ( a [ 0 ] ) NEW_LINE dus = DisjointUnionSets ( n * m ) NEW_LINE for j in range ( 0 , n ) : NEW_LINE INDENT for k in range ( 0 , m ) : NEW_LINE INDENT if a [ j ] [ k ] == 0 : NEW_LINE INDENT continue NEW_LINE DEDENT if j + 1 < n and a [ j + 1 ] [ k ] == 1 : NEW_LINE INDENT dus . Union ( j * ( m ) + k , ( j + 1 ) * ( m ) + k ) NEW_LINE DEDENT if j - 1 >= 0 and a [ j - 1 ] [ k ] == 1 : NEW_LINE INDENT dus . Union ( j * ( m ) + k , ( j - 1 ) * ( m ) + k ) NEW_LINE DEDENT if k + 1 < m and a [ j ] [ k + 1 ] == 1 : NEW_LINE INDENT dus . Union ( j * ( m ) + k , ( j ) * ( m ) + k + 1 ) NEW_LINE DEDENT if k - 1 >= 0 and a [ j ] [ k - 1 ] == 1 : NEW_LINE INDENT dus . Union ( j * ( m ) + k , ( j ) * ( m ) + k - 1 ) NEW_LINE DEDENT if ( j + 1 < n and k + 1 < m and a [ j + 1 ] [ k + 1 ] == 1 ) : NEW_LINE INDENT dus . Union ( j * ( m ) + k , ( j + 1 ) * ( m ) + k + 1 ) NEW_LINE DEDENT if ( j + 1 < n and k - 1 >= 0 and a [ j + 1 ] [ k - 1 ] == 1 ) : NEW_LINE INDENT dus . Union ( j * m + k , ( j + 1 ) * ( m ) + k - 1 ) NEW_LINE DEDENT if ( j - 1 >= 0 and k + 1 < m and a [ j - 1 ] [ k + 1 ] == 1 ) : NEW_LINE INDENT dus . Union ( j * m + k , ( j - 1 ) * m + k + 1 ) NEW_LINE DEDENT if ( j - 1 >= 0 and k - 1 >= 0 and a [ j - 1 ] [ k - 1 ] == 1 ) : NEW_LINE INDENT dus . Union ( j * m + k , ( j - 1 ) * m + k - 1 ) NEW_LINE DEDENT DEDENT DEDENT c = [ 0 ] * ( n * m ) NEW_LINE numberOfIslands = 0 NEW_LINE for j in range ( n ) : NEW_LINE INDENT for k in range ( n ) : NEW_LINE INDENT if a [ j ] [ k ] == 1 : NEW_LINE INDENT x = dus . find ( j * m + k ) NEW_LINE if c [ x ] == 0 : NEW_LINE INDENT numberOfIslands += 1 NEW_LINE c [ x ] += 1 NEW_LINE DEDENT else : NEW_LINE INDENT c [ x ] += 1 NEW_LINE DEDENT DEDENT DEDENT DEDENT return numberOfIslands NEW_LINE DEDENT a = [ [ 1 , 1 , 0 , 0 , 0 ] , [ 0 , 1 , 0 , 0 , 1 ] , [ 1 , 0 , 0 , 1 , 1 ] , [ 0 , 0 , 0 , 0 , 0 ] , [ 1 , 0 , 1 , 0 , 1 ] ] NEW_LINE print ( " Number ▁ of ▁ Islands ▁ is : " , countIslands ( a ) ) NEW_LINE