Accounts Merge（账户合并）

题目 / Problem

中文： 给定账户列表 accounts。每个 accounts[i] 都是一个字符串数组，其中第一个元素是姓名，其余元素是该账户包含的邮箱地址。

如果两个账户至少共享一个邮箱，那么它们一定属于同一个人。即使两个账户的姓名相同，也不一定属于同一个人，因为不同的人可能同名。

合并后，每个账户的第一个元素是姓名，其余元素是按字典序排列的邮箱。账户之间可以按任意顺序返回。

English: Given a list of accounts, each accounts[i] contains a name followed by one or more email addresses.

Two accounts definitely belong to the same person if they share at least one email. Accounts with the same name do not necessarily belong to the same person because different people may have the same name.

After merging, each account must contain the name followed by its emails in sorted order. The merged accounts may be returned in any order.

示例 / Examples

Example 1

Input:
accounts = [
  ["John","johnsmith@mail.com","john_newyork@mail.com"],
  ["John","johnsmith@mail.com","john00@mail.com"],
  ["Mary","mary@mail.com"],
  ["John","johnnybravo@mail.com"]
]

Output:
[
  ["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"],
  ["Mary","mary@mail.com"],
  ["John","johnnybravo@mail.com"]
]

前两个 John 账户共享 johnsmith@mail.com，因此需要合并。最后一个 John 没有与它们共享邮箱，所以仍是独立账户。
The first two John accounts share johnsmith@mail.com, so they are merged. The last John shares no email with them and remains separate.

Example 2

Input:
accounts = [
  ["Gabe","Gabe0@m.co","Gabe3@m.co","Gabe1@m.co"],
  ["Kevin","Kevin3@m.co","Kevin5@m.co","Kevin0@m.co"],
  ["Ethan","Ethan5@m.co","Ethan4@m.co","Ethan0@m.co"],
  ["Hanzo","Hanzo3@m.co","Hanzo1@m.co","Hanzo0@m.co"],
  ["Fern","Fern5@m.co","Fern1@m.co","Fern0@m.co"]
]

Output:
[
  ["Ethan","Ethan0@m.co","Ethan4@m.co","Ethan5@m.co"],
  ["Gabe","Gabe0@m.co","Gabe1@m.co","Gabe3@m.co"],
  ["Hanzo","Hanzo0@m.co","Hanzo1@m.co","Hanzo3@m.co"],
  ["Kevin","Kevin0@m.co","Kevin3@m.co","Kevin5@m.co"],
  ["Fern","Fern0@m.co","Fern1@m.co","Fern5@m.co"]
]

约束 / Constraints

1 <= accounts.length <= 1000
2 <= accounts[i].length <= 10
1 <= accounts[i][j].length <= 30
accounts[i][0] 只包含英文字母。
accounts[i][0] consists only of English letters.
当 j > 0 时，accounts[i][j] 是有效邮箱地址。
For j > 0, accounts[i][j] is a valid email address.

核心性质：传递合并 / Core Property: Transitive Merging

共享邮箱的关系具有传递性：
The shared-email relationship is transitive:

账户 A 与账户 B 共享邮箱
Account A shares an email with Account B

账户 B 与账户 C 共享另一个邮箱
Account B shares another email with Account C

              ↓

A、B、C 都属于同一个人
A, B, and C belong to the same person

即使账户 A 和 C 没有直接共享邮箱，它们也必须被合并。因此，本题可以看作寻找无向图的连通分量，也可以用并查集维护这些连通关系。
Even if A and C do not directly share an email, they must still be merged. The problem can therefore be viewed as finding connected components, or solved with a disjoint-set union structure.

解题思路：并查集 / Approach: Union Find

把每个原始账户的下标视为一个节点。使用 emailOwner 记录每个邮箱第一次出现在哪个账户中：
Treat each original account index as a node. Use emailOwner to record the first account in which each email appears:

email → first account index

遍历账户中的每个邮箱：
For every email in every account:

如果邮箱第一次出现，记录 emailOwner.set(email, accountIndex)。
If it is new, store emailOwner.set(email, accountIndex).
如果邮箱已经出现，说明当前账户与原账户属于同一个人，将两个账户执行 union。
If it already exists, the current account and its previous owner belong to the same person, so union their indices.

完成合并后，再遍历 emailOwner：找到每个账户的根节点，并把邮箱收集到对应的根节点下。最后对每组邮箱排序并加上姓名。
After all unions, iterate through emailOwner again. Find the root of each account and collect the email under that root. Finally, sort each group of emails and prepend the account name.

并查集结构 / Disjoint-Set Structure

并查集提供两个核心操作：
Union Find provides two core operations:

find(x)：找到节点 x 所属集合的代表节点，并使用路径压缩。
find(x): find the representative of x's set using path compression.
union(a, b)：把两个集合合并，并使用按大小合并减少树高。
union(a, b): merge two sets using union by size to keep trees shallow.

路径压缩和按大小合并使单次操作的均摊时间接近常数。
Path compression and union by size make each operation nearly constant in amortized time.

JavaScript 实现 / JavaScript Implementation

/**
 * @param {string[][]} accounts
 * @return {string[][]}
 */
function accountsMerge(accounts) {
  const parent = Array.from(
    { length: accounts.length },
    (_, index) => index
  );
  const size = new Array(accounts.length).fill(1);

  function find(node) {
    if (parent[node] !== node) {
      parent[node] = find(parent[node]);
    }

    return parent[node];
  }

  function union(first, second) {
    let rootFirst = find(first);
    let rootSecond = find(second);

    if (rootFirst === rootSecond) {
      return;
    }

    if (size[rootFirst] < size[rootSecond]) {
      [rootFirst, rootSecond] = [rootSecond, rootFirst];
    }

    parent[rootSecond] = rootFirst;
    size[rootFirst] += size[rootSecond];
  }

  const emailOwner = new Map();

  // 通过共享邮箱合并账户
  // Union accounts that share an email
  for (let accountIndex = 0; accountIndex < accounts.length; accountIndex++) {
    for (let emailIndex = 1; emailIndex < accounts[accountIndex].length; emailIndex++) {
      const email = accounts[accountIndex][emailIndex];

      if (emailOwner.has(email)) {
        union(accountIndex, emailOwner.get(email));
      } else {
        emailOwner.set(email, accountIndex);
      }
    }
  }

  const emailsByRoot = new Map();

  // 按并查集根节点收集所有唯一邮箱
  // Collect unique emails under their component roots
  for (const [email, owner] of emailOwner) {
    const root = find(owner);

    if (!emailsByRoot.has(root)) {
      emailsByRoot.set(root, []);
    }

    emailsByRoot.get(root).push(email);
  }

  const result = [];

  for (const [root, emails] of emailsByRoot) {
    emails.sort();
    result.push([accounts[root][0], ...emails]);
  }

  return result;
}

执行过程 / Walkthrough

以 Example 1 的前两个账户为例：
Consider the first two accounts in Example 1:

账户 0 / Account 0:
["John", "johnsmith@mail.com", "john_newyork@mail.com"]

账户 1 / Account 1:
["John", "johnsmith@mail.com", "john00@mail.com"]

遍历过程：
Traversal:

邮箱 / Email	处理 / Action
`johnsmith@mail.com`（账户 0）	首次出现，记录所有者 `0` / Store owner `0`
`john_newyork@mail.com`	首次出现，记录所有者 `0` / Store owner `0`
`johnsmith@mail.com`（账户 1）	已属于账户 `0`，执行 `union(1, 0)`
`john00@mail.com`	首次出现，记录所有者 `1` / Store owner `1`

合并后，账户 0 和账户 1 具有同一个根节点，因此三个唯一邮箱会被收集到同一组：
After the union, accounts 0 and 1 have the same root, so all three unique emails are collected into one group:

["John",
 "john00@mail.com",
 "john_newyork@mail.com",
 "johnsmith@mail.com"]

为什么不能只按姓名合并？ / Why Not Merge by Name?

姓名不是账户所有者的唯一标识。两个不同的人可能同名，因此姓名相同不能证明账户属于同一个人。
A name is not a unique identifier. Different people may share the same name, so matching names do not prove that accounts belong to the same person.

本题唯一可靠的合并依据是共享邮箱。
The only reliable merge condition in this problem is a shared email.

复杂度 / Complexity

设：
Let:

A 为账户数量。
A be the number of accounts.
E 为所有账户中的邮箱条目总数（包括在不同账户中重复出现的邮箱）。
E be the total number of email entries across all accounts, including repeated occurrences.

并查集操作的均摊复杂度为 O(α(A))，其中 α 是增长极慢的反阿克曼函数，可视为接近常数。
Union-Find operations take amortized O(α(A)), where α is the extremely slow-growing inverse Ackermann function and is effectively constant.

合并账户 / Union accounts: O(E × α(A))
排序邮箱 / Sort emails: 最坏为 O(E log E)
At worst, O(E log E).
总时间复杂度 / Total time: O(E log E)
空间复杂度 / Space: O(A + E)

易错点 / Common Pitfalls

不能根据姓名合并账户，只能根据共享邮箱建立连接。
Do not merge by name; connect accounts only through shared emails.
合并关系具有传递性，不能只合并直接共享邮箱的两个列表后就停止。
Merging is transitive, so direct pairwise overlap is not the whole result.
accounts[i][0] 是姓名，邮箱遍历必须从下标 1 开始。
accounts[i][0] is the name, so email iteration must begin at index 1.
最终必须对每个合并账户中的邮箱按字典序排序。
Sort the emails in every merged account lexicographically.
结果中的账户顺序不限，但每个账户内部必须先放姓名。
Account order is arbitrary, but each result entry must begin with the name.
收集邮箱时要再次调用 find(owner)，不能直接使用可能尚未压缩的 parent[owner]。
Call find(owner) while grouping emails instead of using a possibly stale parent[owner] directly.

Accounts Merge