交互式认知学习实验室

第八章 · 图与并查集 · Unit 12

仅本次页面有效
CH 08
Unit 12实体归并
LeetCode #721 · Accounts Merge

同名不是同一人；
共享标识符才会把账户连成一个实体。

把账户行视为节点，把共享邮箱视为连接证据。哈希表负责发现重复邮箱，并查集负责维护传递性的账户归并，最后必须按最终根节点重新聚合邮箱。

12
账户合并

email → account
account → root
root → sorted emails

检测到历史学习现场

LeetCode #721 原题

给定若干账户。每个账户的第一个字符串是姓名，其余字符串是邮箱。同一邮箱出现在两个账户中，能够确定这两个账户属于同一人；连接关系具有传递性。合并后，每组先放姓名，再放按字典序排列的邮箱。不同人可以同名，结果组的顺序不限。

输入：[["John","johnsmith@mail.com","john_newyork@mail.com"], ["John","johnsmith@mail.com","john00@mail.com"], ["Mary","mary@mail.com"], ["John","johnnybravo@mail.com"]] 输出之一： [["John","john00@mail.com","john_newyork@mail.com","johnsmith@mail.com"], ["Mary","mary@mail.com"], ["John","johnnybravo@mail.com"]]

约束与接口

  • 1 ≤ accounts.length ≤ 1000
  • 2 ≤ accounts[i].length ≤ 10
  • 姓名由英文字母构成，后续字符串均为有效邮箱。
  • 同一人的初始账户具有相同姓名，但同名不代表同一人。
class Solution: def accountsMerge(self, accounts: list[list[str]]) -> list[list[str]]:
实体 identity

题目真正要恢复的“同一人”。不能由姓名唯一确定。

标识符 identifier

邮箱是跨账户连接证据；共享邮箱触发 union。

代表元 root

并查集用根节点表示当前账户所属实体。

重聚合 regroup

合并完成后，必须对每个邮箱重新 find 并按根收集。