問題概要

複数のアカウント情報が「名前, メール1, メール2, …」という形式で与えられる。同一人物のアカウントは少なくとも1つのメールアドレスが共通しているため、それらを1つにまとめて返却せよ。

Union-Findを用いた解法

「共通のメールアドレスを持つアカウントは同一人物」という条件は、「同一要素を含む集合をすべて結合」というUnion-Findの典型的な利用シーンである。

手順

1. 各アカウントを初期状態では独立した集合として扱う。
2. メールアドレスをキーとして、そのアドレスを持つアカウントのインデックスを記録する。
3. 同一メールアドレスを共有するアカウントをすべて結合する。
4. 結合後、代表アカウントごとにメールアドレスを収集・重複除去・ソートし、結果を構築する。

実装例 (C++)

class AccountMerger {
public:
    vector<int> parent;

    int root(int x) {
        if (parent[x] != x) parent[x] = root(parent[x]);
        return parent[x];
    }

    vector<vector<string>> merge(vector<vector<string>>& data) {
        int n = data.size();
        parent.resize(n);
        for (int i = 0; i < n; ++i) parent[i] = i;

        // メールアドレス → 所属アカウントID
        unordered_map<string, vector<int>> mailToIds;
        for (int id = 0; id < n; ++id) {
            for (size_t k = 1; k < data[id].size(); ++k) {
                mailToIds[data[id][k]].push_back(id);
            }
        }

        // Union-Findで結合
        for (auto& [mail, ids] : mailToIds) {
            int leader = root(ids[0]);
            for (size_t i = 1; i < ids.size(); ++i) {
                parent[root(ids[i])] = leader;
            }
        }

        // 代表アカウントID → メールアドレスの集合
        unordered_map<int, set<string>> groupMails;
        for (int id = 0; id < n; ++id) {
            int r = root(id);
            for (size_t k = 1; k < data[id].size(); ++k) {
                groupMails[r].insert(data[id][k]);
            }
        }

        // 結果構築
        vector<vector<string>> ans;
        for (auto& [rootId, mails] : groupMails) {
            vector<string> record = {data[rootId][0]};
            record.insert(record.end(), mails.begin(), mails.end());
            ans.push_back(std::move(record));
        }
        return ans;
    }
};

DFS/グラフ構築による別アプローチ

Union-Find以外に、メールアドレスをノードとし「同一アカウントに含まれるメール同士を無向辺で結ぶ」グラフを構築し、連結成分ごとにまとめる方法もある。

class GraphSolver {
public:
    vector<vector<string>> merge(vector<vector<string>>& accounts) {
        unordered_map<string, vector<string>> adj;
        for (auto& acc : accounts) {
            string firstMail = acc[1];
            for (size_t i = 2; i < acc.size(); ++i) {
                adj[firstMail].push_back(acc[i]);
                adj[acc[i]].push_back(firstMail);
            }
        }

        unordered_set<string> seen;
        vector<vector<string>> res;

        for (auto& acc : accounts) {
            string start = acc[1];
            if (seen.count(start)) continue;

            vector<string> component;
            stack<string> st;
            st.push(start);
            seen.insert(start);

            while (!st.empty()) {
                string cur = st.top(); st.pop();
                component.push_back(cur);
                for (string nxt : adj[cur]) {
                    if (!seen.count(nxt)) {
                        seen.insert(nxt);
                        st.push(nxt);
                    }
                }
            }

            sort(component.begin(), component.end());
            component.insert(component.begin(), acc[0]);
            res.push_back(std::move(component));
        }
        return res;
    }
};

Union-Find版はO(N α(N))、DFS版はO(N log N)（ソート分）で動作し、どちらも十分高速である。