<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>

# class Solution:
#     def numIslands(self, grid: List[List[str]]) -> int:
#         visited = set()
#         rows = len(grid)
#         cols = len(grid[0])

#         def bfs(r, c):
#             queue = deque() 
#             visited.add((r, c))
#             queue.append((r, c))

#             while queue: 
#                 row, col = queue.popleft()
#                 directions = [[1,0], [-1, 0], [0, 1], [0, -1]]

#                 for dr, dc in directions:
#                     r, c = row + dr, col + dc
#                     if 0 <= r < rows and 0 <= c < cols and grid[r][c] == "1" and (r, c) not in visited:
#                         queue.append ((r, c))
#                         visited.add((r,c))

#         islands  = 0 

#         for r in range(rows):
#             for c in range(cols):
#                 if grid[r][c] == "1" and (r, c) not in visited:
#                     islands += 1
#                     bfs(r, c)
#         return islands 
    

class DSU(object):
    def __init__(self):
        self.parents = {}
        self.n = 0 # number of sets
    def add(self, x):
        self.n += 1
        self.parents[x] = x
    def find(self,x): # returns the head of list
        if self.parents[x] != x:
            return self.find(self.parents[x])
        return x
    
    def union(self, a, b):
        a, b = self.find(a), self.find(b)
        if a == b: # if elements in the same island already, there's no need to union them
            return
        self.parents[b] = a
        self.n -= 1 # number of sets decreased

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        rows = len(grid)
        cols = len(grid[0])
        dsu = DSU()
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    dsu.add(i * cols + j) # if it's 1 we add new island, and maybe we will merge it with attached islands later
                    #we don't need to check for all 4 directions, cuz we moving from left to right and from up to down, so we check only up and left element, and if it's 1 we union with our element
                    if i and grid[i - 1][j] == '1':
                        dsu.union((i - 1) * cols + j, i * cols + j)
                    if j and grid[i][j - 1] == '1':
                        dsu.union(i * cols + j - 1, i * cols + j)

        return dsu.n

        
24786