跳到主要内容

LeetCode 721. 账户合并

本节目标

以邮箱而非姓名作为身份键，用并查集归并共享邮箱的账户。

这是图论综合中“实体通过共享身份键连通”的母题。账户索引是并查集节点，重复出现的邮箱提供连接边。

查看 LeetCode 原题

题意与约束​

每个账户由姓名及至少一个邮箱组成；共享任意邮箱的账户属于同一人，合并后在姓名后列出该组全部邮箱并按字典序排序。姓名不是身份：同名、但没有共享邮箱的账户必须保持分离。题目允许合并结果中各账户组的相对顺序不同。

直接思路与瓶颈​

按姓名分组会错误合并同名用户；两两比较账户邮箱又要反复做集合交集，且难处理 A 与 B、B 与 C 的传递连接。把每个邮箱首次出现的账户记录下来，之后遇到同邮箱即合并两条账户索引，就能在线性扫描中捕获所有直接与传递连接。

图模型与算法推导​

把账户索引 0..n-1 作为并查集元素，firstAccount[email] 映射邮箱第一次出现的索引。扫描账户：首次见到邮箱只记录索引；再次见到则调用 unite(current, firstAccount[email])，其布尔返回值表示两个集合是否真的合并，重复连接不会改变分组。扫描后对每个 (email, account) 以 find(account) 为桶收集邮箱，排序并在该根账户的姓名前缀后输出。

正确性依据​

共享邮箱的两账户被一次 unite 放入同一集合；并查集的等价关系具有传递性，所以由共享邮箱链连接的所有账户最终拥有同一根。反之，算法只会因同一邮箱合并，故同名但不共享邮箱的账户不会被合并。按每个邮箱对应账户的最终根收集，既不会漏掉组内邮箱，也不会把不同集合混入同一组。

样例执行过程​

对 [['Zoe','one@mail.com','shared@mail.com'], ['Zoe','shared@mail.com','two@mail.com'], ['Zoe','two@mail.com','three@mail.com']]：先记录 one -> 0、shared -> 0；扫描账户 1 时遇到 shared，unite(1,0) 成功，记录 two -> 1；扫描账户 2 时 unite(2,1) 成功，记录 three -> 2。最终 find(0)、find(1)、find(2) 相同，按该根收集并排序为 ['Zoe','one@mail.com','shared@mail.com','three@mail.com','two@mail.com']。

代码实现​

C++17
#include <algorithm>
#include <numeric>
#include <string>
#include <unordered_map>
#include <utility>
#include <vector>
using namespace std;

class DisjointSet {
    vector<int> parent;
    vector<int> size;

public:
    explicit DisjointSet(int n) : parent(n), size(n, 1) {
        iota(parent.begin(), parent.end(), 0);
    }

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

    bool unite(int first, int second) {
        int rootFirst = find(first);
        int rootSecond = find(second);
        if (rootFirst == rootSecond) {
            return false;
        }
        if (size[rootFirst] < size[rootSecond]) {
            swap(rootFirst, rootSecond);
        }
        parent[rootSecond] = rootFirst;
        size[rootFirst] += size[rootSecond];
        return true;
    }
};

class Solution {
public:
    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
        const int n = static_cast<int>(accounts.size());
        DisjointSet sets(n);
        unordered_map<string, int> firstAccount;

        for (int i = 0; i < n; i++) {
            for (int j = 1; j < static_cast<int>(accounts[i].size()); j++) {
                const string& email = accounts[i][j];
                auto found = firstAccount.find(email);
                if (found == firstAccount.end()) {
                    firstAccount[email] = i;
                } else {
                    sets.unite(i, found->second);
                }
            }
        }

        vector<vector<string>> groupedEmails(n);
        for (const auto& entry : firstAccount) {
            int root = sets.find(entry.second);
            groupedEmails[root].push_back(entry.first);
        }

        vector<vector<string>> merged;
        for (int i = 0; i < n; i++) {
            if (groupedEmails[i].empty()) {
                continue;
            }
            sort(groupedEmails[i].begin(), groupedEmails[i].end());
            vector<string> account{accounts[i][0]};
            account.insert(
                account.end(), groupedEmails[i].begin(), groupedEmails[i].end());
            merged.push_back(std::move(account));
        }
        return merged;
    }
};

复杂度分析​

设邮箱总出现次数为 m、账户数为 n。映射和并查集操作总计 O(m α(n))，各组排序总计 O(m log m)；邮箱映射、分组和并查集使用 O(m + n) 空间。

边界与易错点​

  • 不能以姓名作为映射键；姓名只用于输出标签。
  • 合并对象是账户索引，邮箱只用于定位首次出现的账户。
  • 分组前需 find 到最终根，链式合并的旧根不能直接当桶。
  • 每组邮箱需排序；不要求外层账户组固定排序。

模式迁移​

把账户替换为任意实体、邮箱替换为共享标识，就得到身份聚类与去重模型。它适合只增不删的连接；若连接会频繁删除，普通并查集不能直接维护。