<p>Given an <code>m x n</code> 2D binary grid <code>grid</code> which represents a map of <code>&#39;1&#39;</code>s (land) and <code>&#39;0&#39;</code>s (water), return <em>the number of islands</em>.</p>

<p>An <strong>island</strong> is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;]
]
<strong>Output:</strong> 1
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> grid = [
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;1&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;0&quot;,&quot;0&quot;],
  [&quot;0&quot;,&quot;0&quot;,&quot;0&quot;,&quot;1&quot;,&quot;1&quot;]
]
<strong>Output:</strong> 3
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>m == grid.length</code></li>
	<li><code>n == grid[i].length</code></li>
	<li><code>1 &lt;= m, n &lt;= 300</code></li>
	<li><code>grid[i][j]</code> is <code>&#39;0&#39;</code> or <code>&#39;1&#39;</code>.</li>
</ul>

def merge_sets(sets):
    merged_sets = []

    while sets:
        # Take the first set from the list
        current_set = sets.pop(0)
        
        # Find all sets that intersect with the current set
        intersecting_sets = [s for s in sets if not current_set.isdisjoint(s)]
        
        # Merge all intersecting sets with the current set
        for s in intersecting_sets:
            current_set.update(s)
            sets.remove(s)
        
        # Add the merged set to the merged_sets list
        merged_sets.append(current_set)
    
    return merged_sets



class Solution:
    joints = []
    def connect(self, new :int, old: int):
        found = False
        for j in self.joints:
            if old in j:
                j.add(new)
                found = True

        if not found:
            self.joints.append({old,new})

            
    # validation: row and col are within the grid and the cell is a land.
    def check_neighbour(self, grid: List[List[str]], row: int, col: int, cnt: int) -> int:
        #print(f"{row} {col} {grid[row][col]} {cnt}")
        if row == 0 and col == 0:
            cnt = 10
            grid[row][col] = str(cnt)
            return cnt
        
        if row - 1 >= 0 and grid[row - 1][col] != '0':
            if (col - 1 >= 0 and grid[row][col - 1] != grid[row - 1][col] and grid[row][col - 1] != '0'):
                #print(f'connect {grid[row][col - 1]} {grid[row - 1][col]} at {row} {col}')
                self.connect(int(grid[row][col - 1]), int(grid[row - 1][col]))          
            grid[row][col] = grid[row - 1][col]

            return cnt

        if col - 1 >= 0 and grid[row][col - 1] != '0':
            grid[row][col] = grid[row][col - 1]
            return cnt
        
        cnt = cnt + 1
        grid[row][col] = str(cnt)
        return cnt


    def numIslands(self, grid: List[List[str]]) -> int:
        num_rows = len(grid)
        num_cols = len(grid[0])

        self.joints = []
        cnt = 9
        for row in range(0, num_rows):
            for col in range(0, num_cols):
                if grid[row][col] == '1':
                    cnt = self.check_neighbour(grid, row, col, cnt)

 #       print(grid)
 #       print(self.joints)
        set_len = len(self.joints)
        prev_len = set_len + 1
        while prev_len != set_len:
            self.joints = merge_sets(self.joints)
            prev_len = set_len
            set_len = len(self.joints)

        ret = cnt - 10 + 1
        #print(ret)

        joint_sum = 0
        for j in self.joints:
            joint_sum += len(j) - 1
    
        #print(joint_sum)
        return ret - joint_sum


20546