[并查集]leetcode721：账户合并(medium)

账户合并(medium)"/>

[并查集]leetcode721：账户合并(medium)

题目：

题解：

本题是并查集的实际应用题，需要把实际问题转换为我们熟悉的并查集，这点很重要，我本人现在就是很缺乏这种能力，至于怎么提升肯定需要大量做题吧。

---

思路：

• 1）构建并查集的模板，然后给n个客户进行并查集的初始化。
• 2）构建一个map用来记录<邮箱，邮箱id>。对于邮箱相等的客户，我们进行id的合并；对于邮箱不同的客户，我们就用map记录。
• 3）再构建一个map用来记录<id，邮箱列表>。我们遍历前一个map，将id在同一个联通量中的邮箱，加入邮箱列表。
• 4）最后再遍历第二个map，用来保存结果。

代码如下：

class UnionFind
{
private:vector<int> father; // 父亲vector<int> len;    // 树的大小
public:UnionFind(int n)    // 构造函数初始化对象{father.resize(n),len.resize(n);for(int i=0;i<n;++i){father[i]=i;    // 初始化时父节点指向本身len[i]=1;       // 初始化时每个树大小为1}}int find(int x)     // 查询树的根{// 在查询所有父节点过程中，顺便进行路径压缩if(father[x]!=x)return father[x]=find(father[x]);else return x;}void merge(int x,int y) // 合并x和y所属的集合{x=find(x),y=find(y);if(x==y)return;     // x和y为同一集合不需要合并// 按秩进行合并，小秩向大秩合并if(len[x]<len[y]){father[x]=y;len[y]+=len[x];} else{father[y]=x;len[x]+=len[y];}       }
};class Solution {
public:vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {int n=accounts.size();// 1、先初始化[0,n-1]号id的并查集UnionFind uf(n);// 2、用rec1来记录<邮箱，邮箱id>，当出现相同的邮箱时，我们把id进行合并，表示为同一客户unordered_map<string,int> rec1;for(int i=0;i<n;++i){   // 遍历id为i的客户的邮箱for(int j=1;j<accounts[i].size();++j){// 判断是否发现重复邮箱。没有出现则把id和emil记录在map中，出现了重复邮箱，则进行id的合并string emil=accounts[i][j];if(rec1.find(emil)==rec1.end())rec1[emil]=i;else uf.merge(i,rec1[emil]);}}// 3、再用一个rec2来记录<联通量根节点id，邮箱列表>unordered_map<int,vector<string>> rec2;for(auto &[k,v]:rec1)// 将同一集合中的邮箱放在一起，由于已经进行了集合的合并，所以不会出现重复的邮箱{rec2[uf.find(v)].emplace_back(k);}// 4、遍历rec2，来得到最后结果vector<vector<string>> res;for(auto& [k,v]:rec2){vector<string> account;// 将客户的姓名添加进去account.push_back(accounts[k][0]);// 将邮箱进行排序sort(v.begin(),v.end());account.insert(account.end(),v.begin(),v.end());res.push_back(account);}return res;}
};