721. Accounts Merge

union-find O(sum(A_ilogA_i)) time O(sum(A_i)) space where A_i = accounts[i].length()
用一个hashmap维护email和其对应的accounts的下标i
当不同account有相同的email时，merge对应的两个下标
最后整理原来accounts每个下标对应的所有email以及name即可

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, int> m;
        int n = accounts.size();
        parent.resize(n);
        iota(begin(parent), end(parent), 0);
        for (int i = 0; i < n; ++i) {
            for (int j = 1; j < accounts[i].size(); ++j) {
                if (m.count(accounts[i][j])) {
                    merge(m[accounts[i][j]], i);
                } else {
                    m[accounts[i][j]] = i;
                }
            }
        }
        vector<set<string>> v(n);
        for (const auto &[s, i] : m) {
            v[find(i)].insert(s); // 归并email
        }
        vector<vector<string>> res;
        for (int i = 0; i < n; ++i) {
            if (v[i].empty()) continue;
            res.push_back({accounts[i][0]}); // 归并email和name
            res.back().insert(end(res.back()), begin(v[i]), end(v[i]));
        }
        return res;
    }

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

    void merge(int x, int y) {
        parent[find(x)] = find(y);
    }

    vector<int> parent;
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, int> email2id;
        unordered_map<string, string> email2name;
        UF uf;
        int id = 0;
        for (const auto &a : accounts) {
            if (a.size() > 1) {
                if (!email2id.count(a[1])) {
                    email2id[a[1]] = id++;
                    email2name[a[1]] = a[0];
                }
                uf.add(email2id[a[1]]);
                for (int i = 2; i < a.size(); ++i) {
                    if (!email2id.count(a[i])) {
                        email2id[a[i]] = id++;
                        email2name[a[i]] = a[0];
                    }
                    uf.add(email2id[a[i]]);
                    uf.merge(email2id[a[1]], email2id[a[i]]);
                }
            }
        }
        unordered_map<int, set<string>> m;
        for (const auto &p : email2id) {
            m[uf.getParent(email2id[p.first])].insert(p.first);
        }
        vector<vector<string>> res;
        for (const auto &p : m) {
            res.push_back({email2name[*p.second.begin()]});
            res.back().insert(res.back().end(), p.second.begin(), p.second.end());
        }
        return res;
    }

    struct UF {
        void add(int x) {
            if (parent.count(x)) return;
            parent[x] = x;
        }

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

        void merge(int x, int y) {
            parent[getParent(x)] = getParent(y);
        }

        unordered_map<int, int> parent;
    };
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        unordered_map<string, pair<string, set<string>>> m;
        UF uf;
        for (const auto &a : accounts) {
            if (a.size() > 1) {
                uf.add(a[1]);
                m[a[1]].first = a[0];
                for (int i = 2; i < a.size(); ++i) {
                    uf.add(a[i]);
                    m[a[i]].first = a[0];
                    uf.merge(a[1], a[i]);
                }
            }
        }
        for (const auto &p : m) {
            m[uf.getParent(p.first)].second.insert(p.first);
        }
        vector<vector<string>> res;
        for (const auto &p : m) {
            if (!p.second.second.empty()) {
                res.push_back({p.second.first});
                res.back().insert(res.back().end(), p.second.second.begin(), p.second.second.end());
            }
        }
        return res;
    }

    struct UF {
        void add(const string &s) {
            if (parent.count(s)) return;
            parent[s] = s;
        }

        string getParent(string s) {
            while (parent[s] != s) {
                s = parent[s] = parent[parent[s]];
            }
            return parent[s];
        }

        void merge(const string &x, const string &y) {
            parent[getParent(x)] = getParent(y);
        }

        unordered_map<string, string> parent;
    };
};