[M并查集] lc721. 账户合并(并查集+并查集变种+dfs+建图+好题)

1. 题目来源

链接：721. 账户合并

• 关联链接
  • [并查集+模板] 裸并查集模板
    
  • 一篇很不错的题解，来自题解区高赞：【详解】并查集

2. 题目解析

睡不着，做做题。
本题很明显看出，一个名称像一个集合，集合元素是所有的邮箱，一个集合和其他集合要合并的前提是，集合内有相同元素。于是引发下面两个思路：

• 集合合并：并查集
• 建图深搜：dfs

不想看这个 dfs 的做法，关于本题 并查集 的做法还是挺有意思的。

• 将每一行初始元素单独看成集合，一开始所有的集合未经合并，都是独立的，用下标表示集合。
• 用每一个 email，做 hash，统计相同 email 的集合有哪些，用 vector 统计出来。
• 这时候就可以用并查集进行集合合并了，将 vector 中大于两个元素的所有集合统一合并起来。更改并查集的父节点存储值，也是集合合并的核心操作。
• email 数据整理。相同集合的 email 用 set 进行累计、去重、排序。
• 结果输出，这个时候一些集合是没有结果的，要特判一下，也不需要对结果进行排序，直接输出即可。

---

• 时间复杂度：$O(n)$
• 空间复杂度：$O(1)$

---

class Solution {
   
public:
    vector<int> p;

    int find(int x) {
      // 并查集默写函数
        if (p[x] != x) return find(p[x]);

        return p[x];
    }

    vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {
   
        int n = accounts.

原文地址：https://blog.csdn.net/yl_puyu/article/details/140426458

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！