Disjoint Set

Let's implement a basic Disjoint Set in Python:

class DisjointSet:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n

    def find(self, x):
        # Find the root parent of the set containing x
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        # Merge the sets containing x and y
        root_x = self.find(x)
        root_y = self.find(y)

        if root_x != root_y:
            if self.rank[root_x] < self.rank[root_y]:
                self.parent[root_x] = root_y
            elif self.rank[root_x] > self.rank[root_y]:
                self.parent[root_y] = root_x
            else:
                self.parent[root_x] = root_y
                self.rank[root_y] += 1

 Now, let's solve a question using the Disjoint Set data structure. The problem we'll solve is "Number of Islands," which asks to count the number of connected islands in a grid.

class DisjointSet:
    # ... (previous implementation remains the same)

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

        rows, cols = len(grid), len(grid[0])
        dsu = DisjointSet(rows * cols)
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        count = 0

        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1':
                    for dx, dy in directions:
                        nx, ny = i + dx, j + dy
                        if 0 <= nx < rows and 0 <= ny < cols and grid[nx][ny] == '1':
                            dsu.union(i * cols + j, nx * cols + ny)

        # Count the number of unique sets in the disjoint set
        for i in range(rows):
            for j in range(cols):
                if grid[i][j] == '1' and dsu.find(i * cols + j) == i * cols + j:
                    count += 1

        return count

In this example, we create a DisjointSet instance dsu and iterate through the grid. If a cell contains '1', we connect it with its neighboring '1' cells using the union operation. After processing all cells, we count the number of unique sets in the disjoint set using the find operation. This count represents the number of islands in the grid.

The time complexity of the find operation is approximately O(log n), where n is the number of elements in the disjoint set. The time complexity of the union operation is also O(log n) on average, but can be O(n) in the worst case. The time complexity of the numIslands method is O(rows * cols * log n), where rows and cols are the dimensions of the grid. The space complexity is O(rows * cols) to store the parent and rank arrays.