Union-Find (Disjoint Set Union)

class UnionFind {
    private int[] parent;
    private int[] rank;
    private int components;

    public UnionFind(int n) {
        parent = new int[n];
        rank   = new int[n];
        components = n;
        for (int i = 0; i < n; i++) parent[i] = i; // each node is its own parent
    }

    // Find with path compression
    public int find(int x) {
        if (parent[x] != x)
            parent[x] = find(parent[x]); // compress: point directly to root
        return parent[x];
    }

    // Union by rank
    public boolean union(int x, int y) {
        int px = find(x), py = find(y);
        if (px == py) return false; // already in same set
        if (rank[px] < rank[py]) { int tmp = px; px = py; py = tmp; } // swap so px has higher rank
        parent[py] = px;
        if (rank[px] == rank[py]) rank[px]++;
        components--;
        return true; // successfully merged
    }

    public boolean connected(int x, int y) { return find(x) == find(y); }
    public int getComponents() { return components; }
}

public int countComponents(int n, int[][] edges) {
    UnionFind uf = new UnionFind(n);
    for (int[] edge : edges) uf.union(edge[0], edge[1]);
    return uf.getComponents();
}

// Find the edge that creates a cycle
public int[] findRedundantConnection(int[][] edges) {
    UnionFind uf = new UnionFind(edges.length + 1);
    for (int[] edge : edges) {
        if (!uf.union(edge[0], edge[1])) return edge; // already connected = cycle edge
    }
    return new int[0];
}

// Merge accounts that share an email
public List<List<String>> accountsMerge(List<List<String>> accounts) {
    Map<String, String> emailToName = new HashMap<>();
    Map<String, String> parent = new HashMap<>();

    // Initialize each email as its own parent
    for (List<String> account : accounts) {
        String name = account.get(0);
        for (int i = 1; i < account.size(); i++) {
            parent.putIfAbsent(account.get(i), account.get(i));
            emailToName.put(account.get(i), name);
        }
    }

    // Union all emails in the same account
    for (List<String> account : accounts) {
        String root = account.get(1);
        for (int i = 2; i < account.size(); i++) {
            String px = find(parent, root);
            String py = find(parent, account.get(i));
            parent.put(px, py);
        }
    }

    // Group by root
    Map<String, TreeSet<String>> groups = new HashMap<>();
    for (String email : parent.keySet()) {
        String root = find(parent, email);
        groups.computeIfAbsent(root, k -> new TreeSet<>()).add(email);
    }

    List<List<String>> result = new ArrayList<>();
    for (Map.Entry<String, TreeSet<String>> e : groups.entrySet()) {
        List<String> account = new ArrayList<>();
        account.add(emailToName.get(e.getKey()));
        account.addAll(e.getValue());
        result.add(account);
    }
    return result;
}