<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 UnionFind:
    def __init__(self, size):
        self.parent = list(range(size))  # Каждый элемент изначально является своим родителем
        self.rank = [1] * size  # Сохраняем ранг (глубину дерева) для оптимизации объединений
        self.count = 0  # Количество отдельных компонентов (островов)

    def find(self, p):
        if self.parent[p] != p:
            self.parent[p] = self.find(self.parent[p])  # Path compression
        return self.parent[p]

    def union(self, p, q):
        rootP = self.find(p)
        rootQ = self.find(q)

        if rootP != rootQ:
            # Union by rank (соединяем менее глубокое дерево к более глубокому)
            if self.rank[rootP] > self.rank[rootQ]:
                self.parent[rootQ] = rootP
            elif self.rank[rootP] < self.rank[rootQ]:
                self.parent[rootP] = rootQ
            else:
                self.parent[rootQ] = rootP
                self.rank[rootP] += 1
            self.count -= 1  # Объединили два острова, уменьшили количество

    def set_count(self, count):
        self.count = count

    def get_count(self):
        return self.count


class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0

        rows, cols = len(grid), len(grid[0])
        uf = UnionFind(rows * cols)

        def get_index(x, y):
            return x * cols + y

        # Инициализация: считаем количество земель
        num_land_cells = 0
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    num_land_cells += 1

        uf.set_count(num_land_cells)  # Устанавливаем начальное количество островов (единичных земель)

        # Проход по сетке и объединение соседей (вверх, вниз, влево, вправо)
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    # Проверяем правого соседа
                    if j + 1 < cols and grid[i][j + 1] == '1':
                        uf.union(get_index(i, j), get_index(i, j + 1))
                    # Проверяем нижнего соседа
                    if i + 1 < rows and grid[i + 1][j] == '1':
                        uf.union(get_index(i, j), get_index(i + 1, j))

        return uf.get_count()

22798