Union-Find is a tree-based data structure designed to handle disjoint sets, supporting operations like merging two sets and querying connectivity. It efficiently addresses problems involving connectivity and merging of non-overlapping collections.

In Union-Find, each set is represented as a tree where each element points to its parent. The root of the tree acts as the representative for the set. The core operations are find to locate the representative of an element and union to merge two sets.

Find Operation The find function determines the root representative of an element. If an element points to itself, it is the root. Otherwise, it recursively follows parent pointers until the root is found.

public int find(int element, int[] parent) {
    while (element != parent[element]) {
        element = parent[element];
    }
    return element;
}

Union Operation The union functon merges two sets by linking their roots. It first finds the roots of both elements and, if they differ, sets one root as the parent of the other.

public void union(int a, int b, int[] parent) {
    int rootA = find(a, parent);
    int rootB = find(b, parent);
    if (rootA != rootB) {
        parent[rootA] = rootB;
    }
}

Path Compresion Optimization To prevent deep trees that degrade query performance, path compression flattens the structure during find. After locating the root, it updates the parent of each visited node directly to the root.

public int findWithCompression(int element, int[] parent) {
    if (element == parent[element]) {
        return element;
    }
    return parent[element] = findWithCompression(parent[element], parent);
}

Union by Rank Optimization When merging sets, union by rank attaches the shorter tree under the taller one to keep the overall height minimal. A rank array tracks tree heights.

public void unionByRank(int a, int b, int[] parent, int[] rank) {
    int rootA = find(a, parent);
    int rootB = find(b, parent);
    if (rootA != rootB) {
        if (rank[rootA] > rank[rootB]) {
            parent[rootB] = rootA;
        } else if (rank[rootA] < rank[rootB]) {
            parent[rootA] = rootB;
        } else {
            parent[rootB] = rootA;
            rank[rootA]++;
        }
    }
}

LeetCode 200: Number of Islands Given a 2D grid where '1' represents land and '0' represents water, count the number of islands. An island is formed by horizontally or vertically adjaccent '1's.

Solution 1: Depth-First Search (DFS) Traverse the grid. When encountering a '1', increment the island count and use DFS to mark all connected '1's as '0'.

public int countIslandsDFS(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int rows = grid.length, cols = grid[0].length;
    int islandCount = 0;
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {
                islandCount++;
                dfsMark(grid, r, c, rows, cols);
            }
        }
    }
    return islandCount;
}

private void dfsMark(char[][] grid, int r, int c, int rows, int cols) {
    if (r < 0 || c < 0 || r >= rows || c >= cols || grid[r][c] == '0') return;
    grid[r][c] = '0';
    dfsMark(grid, r + 1, c, rows, cols);
    dfsMark(grid, r - 1, c, rows, cols);
    dfsMark(grid, r, c + 1, rows, cols);
    dfsMark(grid, r, c - 1, rows, cols);
}

Solution 2: Breadth-First Search (BFS) Use a queue to explore connected '1's level by level, marking them as '0'.

public int countIslandsBFS(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int rows = grid.length, cols = grid[0].length;
    int islandCount = 0;
    Queue<int[]> queue = new LinkedList<>();
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '1') {
                islandCount++;
                grid[r][c] = '0';
                queue.offer(new int[]{r, c});
                while (!queue.isEmpty()) {
                    int[] cell = queue.poll();
                    int x = cell[0], y = cell[1];
                    if (x + 1 < rows && grid[x + 1][y] == '1') {
                        grid[x + 1][y] = '0';
                        queue.offer(new int[]{x + 1, y});
                    }
                    if (x - 1 >= 0 && grid[x - 1][y] == '1') {
                        grid[x - 1][y] = '0';
                        queue.offer(new int[]{x - 1, y});
                    }
                    if (y + 1 < cols && grid[x][y + 1] == '1') {
                        grid[x][y + 1] = '0';
                        queue.offer(new int[]{x, y + 1});
                    }
                    if (y - 1 >= 0 && grid[x][y - 1] == '1') {
                        grid[x][y - 1] = '0';
                        queue.offer(new int[]{x, y - 1});
                    }
                }
            }
        }
    }
    return islandCount;
}

Solution 3: Union-Find Approach Convert the 2D grid to a 1D array. Initialize each land cell as its own set. For each '1', union with adjacent '1's. The island count is total land cells minus union operations.

public int countIslandsUnionFind(char[][] grid) {
    if (grid == null || grid.length == 0) return 0;
    int rows = grid.length, cols = grid[0].length;
    int waterCount = 0;
    UnionFind uf = new UnionFind(grid);
    for (int r = 0; r < rows; r++) {
        for (int c = 0; c < cols; c++) {
            if (grid[r][c] == '0') {
                waterCount++;
            } else {
                int index = r * cols + c;
                if (r + 1 < rows && grid[r + 1][c] == '1') {
                    uf.union(index, (r + 1) * cols + c);
                }
                if (r - 1 >= 0 && grid[r - 1][c] == '1') {
                    uf.union(index, (r - 1) * cols + c);
                }
                if (c + 1 < cols && grid[r][c + 1] == '1') {
                    uf.union(index, r * cols + (c + 1));
                }
                if (c - 1 >= 0 && grid[r][c - 1] == '1') {
                    uf.union(index, r * cols + (c - 1));
                }
            }
        }
    }
    return uf.getSetCount() - waterCount;
}

class UnionFind {
    private int[] parent;
    private int setCount;

    UnionFind(char[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        setCount = rows * cols;
        parent = new int[setCount];
        for (int i = 0; i < setCount; i++) parent[i] = i;
    }

    int find(int x) {
        if (x == parent[x]) return x;
        return parent[x] = find(parent[x]);
    }

    void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            parent[rootX] = rootY;
            setCount--;
        }
    }

    int getSetCount() {
        return setCount;
    }
}