721

class Solution {
public:
    struct UnionFind {
        UnionFind(const int n)
            : parent(n), rank(n, 1) {
                for (int i = 0 ; i < n ; ++i)
                    parent[i] = i;
            }

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

        void merge(int u, int v) {
            u = find(u);
            v = find(v);
            if (u == v) return;
            if (rank[u] > rank[v]) swap(u, v);
            parent[u] = v;
            if (rank[u] == rank[v]) ++rank[v];
        }

        vector<int> parent;
        vector<int> rank;
    };

    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        const int n = accounts.size();
        unordered_map<string, int> emailMapping;
        UnionFind uf {n};

        int user = 0;
        for (auto& a : accounts) {
            for (int i = 1 ; i < a.size() ; ++i) {
                auto it = emailMapping.find(a[i]);
                if (it == emailMapping.end())
                    emailMapping[a[i]] = user;
                else
                    uf.merge(user, it->second);
            }
            ++user;
        }

        vector<vector<string>> res (n, vector<string> {""});
        for (auto& p : emailMapping) {
            const int userId = uf.find(p.second);
            res[userId].emplace_back(string {p.first});
        }  // End for

        int i = 0, j = 0;
        while (i < n) {
            if (res[i].size() > 1) {
                sort(res[i].begin(), res[i].end());
                res[i][0] = accounts[i][0];
                swap(res[i], res[j++]);
            }
            ++i;
        }
        res.resize(j);
        return res;
    }
};