Union Find (Disjoint Set Union)

public class UnionFind {
    private int[] parent;  // parent[i] = parent of i
    private int[] rank;    // rank[i] = approximate depth of tree rooted at i
    private int count;     // number of connected components
    public UnionFind(int n) {
        parent = new int[n];
        rank = new int[n];
        count = n;
        // Initially, each element is its own parent (separate set)
        for (int i = 0; i < n; i++) {
            parent[i] = i;
            rank[i] = 0;
        }
    }
    // Find with path compression
    public int find(int x) {
        if (parent[x] != x) {
            // Path compression: make x point directly to root
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }
    // Union by rank
    public boolean union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX == rootY) {
            return false;  // Already in same set
        }
        // Union by rank: attach smaller tree under larger
        if (rank[rootX] < rank[rootY]) {
            parent[rootX] = rootY;
        } else if (rank[rootX] > rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
        count--;
        return true;
    }
    // Check if x and y are connected
    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }
    // Get number of connected components
    public int getCount() {
        return count;
    }
    public static void main(String[] args) {
        UnionFind uf = new UnionFind(5);
        System.out.println("Initial components: " + uf.getCount());  // 5
        uf.union(0, 1);
        uf.union(1, 2);
        System.out.println("After unions: " + uf.getCount());  // 3
        System.out.println("0 and 2 connected: " + uf.connected(0, 2));  // true
        System.out.println("0 and 3 connected: " + uf.connected(0, 3));  // false
    }
}

public class NumberOfIslands {
    public static int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }
        int rows = grid.length;
        int cols = grid[0].length;
        UnionFind uf = new UnionFind(rows * cols);
        int waterCount = 0;
        // Process each cell
        for (int r = 0; r < rows; r++) {
            for (int c = 0; c < cols; c++) {
                if (grid[r][c] == '0') {
                    waterCount++;
                    continue;
                }
                // Connect with adjacent land cells
                int id = r * cols + c;
                // Check right
                if (c + 1 < cols && grid[r][c + 1] == '1') {
                    uf.union(id, r * cols + c + 1);
                }
                // Check down
                if (r + 1 < rows && grid[r + 1][c] == '1') {
                    uf.union(id, (r + 1) * cols + c);
                }
            }
        }
        // Islands = components - water cells
        return uf.getCount() - waterCount;
    }
    public static void main(String[] args) {
        char[][] grid = {
            {'1', '1', '0', '0', '0'},
            {'1', '1', '0', '0', '0'},
            {'0', '0', '1', '0', '0'},
            {'0', '0', '0', '1', '1'}
        };
        System.out.println("Number of islands: " + numIslands(grid));
        // Output: 3
    }
}

public class RedundantConnection {
    public static int[] findRedundantConnection(int[][] edges) {
        int n = edges.length;
        UnionFind uf = new UnionFind(n + 1);  // Nodes are 1-indexed
        for (int[] edge : edges) {
            int u = edge[0];
            int v = edge[1];
            // If already connected, this edge creates a cycle
            if (!uf.union(u, v)) {
                return edge;  // This is the redundant edge
            }
        }
        return new int[]{};
    }
    // Friend Circles / Number of Provinces
    public static int findCircleNum(int[][] isConnected) {
        int n = isConnected.length;
        UnionFind uf = new UnionFind(n);
        // Union friends
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (isConnected[i][j] == 1) {
                    uf.union(i, j);
                }
            }
        }
        return uf.getCount();
    }
    // Accounts Merge (more complex example)
    public static int accountsMerge(String[][] accounts) {
        UnionFind uf = new UnionFind(accounts.length);
        // Map email to account index
        java.util.Map<String, Integer> emailToId = new java.util.HashMap<>();
        for (int i = 0; i < accounts.length; i++) {
            for (int j = 1; j < accounts[i].length; j++) {
                String email = accounts[i][j];
                if (emailToId.containsKey(email)) {
                    // Merge this account with previous account having this email
                    uf.union(i, emailToId.get(email));
                } else {
                    emailToId.put(email, i);
                }
            }
        }
        return uf.getCount();
    }
    public static void main(String[] args) {
        int[][] edges = {{1, 2}, {1, 3}, {2, 3}};
        int[] redundant = findRedundantConnection(edges);
        System.out.println("Redundant edge: [" + redundant[0] + ", " + redundant[1] + "]");
        // Output: [2, 3] (creates cycle with 1-2-3)
        int[][] friends = {
            {1, 1, 0},
            {1, 1, 0},
            {0, 0, 1}
        };
        System.out.println("Friend circles: " + findCircleNum(friends));
        // Output: 2 (groups: {0,1} and {2})
    }
}