LeetCode 721. 账户合并

题目描述：
给定一个账户列表，每个账户包含一个名称和一个邮箱列表。现在需要合并这些账户：如果两个账户共享至少一个共同的邮箱，那么这两个账户属于同一个人，应该被合并。合并后的账户包含所有邮箱（去重），并且按字典序排列。名称相同的账户不一定属于同一个人，判断依据是邮箱是否相同。

解题过程：

1. 问题分析

• 我们需要将具有共同邮箱的账户进行合并
• 这本质上是一个连通性问题：如果两个账户有相同的邮箱，它们就应该连接在一起
• 最终需要将连通的所有账户合并，并对邮箱排序去重

2. 构建图结构

• 将每个邮箱看作图中的一个节点
• 对于每个账户中的邮箱列表，将第一个邮箱与其他所有邮箱双向连接
• 这样，同一个账户内的所有邮箱都相互连通
• 不同账户间如果有相同邮箱，也会通过这些公共邮箱连通

3. 使用并查集合并

• 初始化并查集，每个邮箱初始时属于不同的集合
• 遍历每个账户：
  • 将该账户的第一个邮箱作为根节点
  • 将该账户中其他所有邮箱都与这个根节点合并
• 这样，所有连通的邮箱都会被合并到同一个集合中

4. 收集合并结果

• 遍历所有邮箱，找到每个邮箱所属的根节点
• 将同一个根节点下的所有邮箱收集到一起
• 对每个集合的邮箱进行排序和去重
• 将根节点对应的账户名称作为合并后账户的名称

5. 输出结果

• 对每个合并后的账户，按照题目要求的格式输出
• 名称在前，后面跟着排序后的邮箱列表

这个算法的关键在于将邮箱作为图的节点，通过并查集高效地找到所有连通的邮箱集合，最终完成账户的合并。时间复杂度主要取决于并查集操作和排序操作，整体效率较高。