Accounts Merge

class Solution {
    vector<int> parent;
    int find(int x) { while (parent[x] != x) { parent[x] = parent[parent[x]]; x = parent[x]; } return x; }
    void unite(int a, int b) { parent[find(a)] = find(b); }
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        int n = accounts.size();
        parent.resize(n);
        iota(parent.begin(), parent.end(), 0);
        unordered_map<string,int> owner;
        for (int i = 0; i < n; ++i) {
            for (int j = 1; j < (int)accounts[i].size(); ++j) {
                auto it = owner.find(accounts[i][j]);
                if (it == owner.end()) owner[accounts[i][j]] = i;
                else unite(i, it->second);
            }
        }
        unordered_map<int, set<string>> byRoot;
        for (auto& [e, i] : owner) byRoot[find(i)].insert(e);
        vector<vector<string>> ans;
        for (auto& [root, emails] : byRoot) {
            vector<string> row;
            row.push_back(accounts[root][0]);
            row.insert(row.end(), emails.begin(), emails.end());
            ans.push_back(std::move(row));
        }
        return ans;
    }
};

func accountsMerge(accounts [][]string) [][]string {
    n := len(accounts)
    parent := make([]int, n)
    for i := range parent {
        parent[i] = i
    }
    var find func(int) int
    find = func(x int) int {
        for parent[x] != x {
            parent[x] = parent[parent[x]]
            x = parent[x]
        }
        return x
    }
    unite := func(a, b int) { parent[find(a)] = find(b) }
    owner := make(map[string]int)
    for i := 0; i < n; i++ {
        for j := 1; j < len(accounts[i]); j++ {
            e := accounts[i][j]
            if prev, ok := owner[e]; ok {
                unite(i, prev)
            } else {
                owner[e] = i
            }
        }
    }
    byRoot := make(map[int]map[string]bool)
    for e, i := range owner {
        r := find(i)
        if byRoot[r] == nil {
            byRoot[r] = make(map[string]bool)
        }
        byRoot[r][e] = true
    }
    ans := [][]string{}
    for root, emails := range byRoot {
        sorted := make([]string, 0, len(emails))
        for e := range emails {
            sorted = append(sorted, e)
        }
        sort.Strings(sorted)
        row := append([]string{accounts[root][0]}, sorted...)
        ans = append(ans, row)
    }
    return ans
}

from collections import defaultdict
from typing import List

class Solution:
    def accountsMerge(self, accounts: List[List[str]]) -> List[List[str]]:
        n = len(accounts)
        parent = list(range(n))

        def find(x: int) -> int:
            while parent[x] != x:
                parent[x] = parent[parent[x]]
                x = parent[x]
            return x

        def unite(a: int, b: int) -> None:
            parent[find(a)] = find(b)

        owner: dict[str, int] = {}
        for i in range(n):
            for e in accounts[i][1:]:
                if e in owner:
                    unite(i, owner[e])
                else:
                    owner[e] = i

        by_root: dict[int, set[str]] = defaultdict(set)
        for e, i in owner.items():
            by_root[find(i)].add(e)

        ans: List[List[str]] = []
        for root, emails in by_root.items():
            ans.append([accounts[root][0]] + sorted(emails))
        return ans

var accountsMerge = function(accounts) {
    const n = accounts.length;
    const parent = Array.from({ length: n }, (_, i) => i);
    const find = (x) => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    const unite = (a, b) => { parent[find(a)] = find(b); };
    const owner = new Map();
    for (let i = 0; i < n; i++) {
        for (let j = 1; j < accounts[i].length; j++) {
            const e = accounts[i][j];
            if (owner.has(e)) unite(i, owner.get(e));
            else owner.set(e, i);
        }
    }
    const byRoot = new Map();
    for (const [e, i] of owner) {
        const r = find(i);
        if (!byRoot.has(r)) byRoot.set(r, []);
        byRoot.get(r).push(e);
    }
    const ans = [];
    for (const [root, emails] of byRoot) {
        emails.sort();
        ans.push([accounts[root][0], ...emails]);
    }
    return ans;
};

class Solution {
    private int[] parent;

    private int find(int x) {
        while (parent[x] != x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    }

    private void unite(int a, int b) {
        parent[find(a)] = find(b);
    }

    public List<List<String>> accountsMerge(List<List<String>> accounts) {
        int n = accounts.size();
        parent = new int[n];
        for (int i = 0; i < n; i++) parent[i] = i;
        Map<String, Integer> owner = new HashMap<>();
        for (int i = 0; i < n; i++) {
            List<String> acc = accounts.get(i);
            for (int j = 1; j < acc.size(); j++) {
                String e = acc.get(j);
                Integer prev = owner.get(e);
                if (prev == null) owner.put(e, i);
                else unite(i, prev);
            }
        }
        Map<Integer, TreeSet<String>> byRoot = new HashMap<>();
        for (Map.Entry<String, Integer> en : owner.entrySet()) {
            int r = find(en.getValue());
            byRoot.computeIfAbsent(r, k -> new TreeSet<>()).add(en.getKey());
        }
        List<List<String>> ans = new ArrayList<>();
        for (Map.Entry<Integer, TreeSet<String>> en : byRoot.entrySet()) {
            List<String> row = new ArrayList<>();
            row.add(accounts.get(en.getKey()).get(0));
            row.addAll(en.getValue());
            ans.add(row);
        }
        return ans;
    }
}

function accountsMerge(accounts: string[][]): string[][] {
    const n = accounts.length;
    const parent: number[] = Array.from({ length: n }, (_, i) => i);
    const find = (x: number): number => {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]];
            x = parent[x];
        }
        return x;
    };
    const unite = (a: number, b: number): void => { parent[find(a)] = find(b); };
    const owner = new Map<string, number>();
    for (let i = 0; i < n; i++) {
        for (let j = 1; j < accounts[i].length; j++) {
            const e = accounts[i][j];
            if (owner.has(e)) unite(i, owner.get(e)!);
            else owner.set(e, i);
        }
    }
    const byRoot = new Map<number, string[]>();
    for (const [e, i] of owner) {
        const r = find(i);
        if (!byRoot.has(r)) byRoot.set(r, []);
        byRoot.get(r)!.push(e);
    }
    const ans: string[][] = [];
    for (const [root, emails] of byRoot) {
        emails.sort();
        ans.push([accounts[root][0], ...emails]);
    }
    return ans;
}