给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该帐户的邮箱地址。
现在，我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址，则两个帐户必定属于同一个人。请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，但其所有帐户都具有相同的名称。
合并帐户后，按以下格式返回帐户：每个帐户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。
例子 1:
Input: accounts = [["John", "johnsmith@mail.com", "john00@mail.com"], ["John", "johnnybravo@mail.com"], ["John", "johnsmith@mail.com", "john_newyork@mail.com"], ["Mary", "mary@mail.com"]] Output: [["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'], ["John", "johnnybravo@mail.com"], ["Mary", "mary@mail.com"]] Explanation: 第一个和第三个 John 是同一个人，因为他们有共同的电子邮件 "johnsmith@mail.com"。 第二个 John 和 Mary 是不同的人，因为他们的电子邮件地址没有被其他帐户使用。 我们可以以任何顺序返回这些列表，例如答案[['Mary'，'mary@mail.com']，['John'，'johnnybravo@mail.com']， ['John'，'john00@mail.com'，'john_newyork@mail.com'，'johnsmith@mail.com']]仍然会被接受。
注意：
accounts的长度将在[1，1000]的范围内。accounts[i]的长度将在[1，10]的范围内。accounts[i][j]的长度将在[1，30]的范围内。
思路：这道题是并查集的考查。但是对于具体的实现方法，还是要多多想想。我一开始想的是，将列表中，每组的每个邮箱的父亲设为第一个元素，也就是accounts[i][0]。但是因为有重名的原因，这样的话没法进行合并，因为例子中，显然第一个和第三个的John是一个人，而第二个John是另外一个人，所以好像邮箱才是用来区分人的元素。
如何找到并查集中所谓的父亲节点是主要的问题，既然不能用名字，那么我们就用每组邮箱中的第一个邮箱来作为这一组的上级（父亲）。
首先我们需要初始化，每个邮箱的父亲是自己，而且还要存储一下每组的拥有者，就是accounts[i][0]。然后遍历，将每一组的邮箱的父亲都设为该组的第一个邮箱。接着利用map来操作（主要利用它的唯一性）map<string, set<string>>，第一个用来存祖宗，第二个用来存该祖宗下的所有子节点（即第一个存的是祖宗邮箱，第二个存的是祖宗是该邮箱的所有邮箱，包括它本身），遍历每个邮箱，将邮箱插入到map中。这里我们注意，虽然是个简单的插入过程，但是，实际的操作是：如果map中存在这个祖宗节点，那么将该邮箱直接插入到其后面的子集中，如果不存在，将该邮箱的祖宗以及自己本身放到map中。
为什么又出来个祖宗节点呢，因为每组的父亲只是第一个邮箱，如果该邮箱出现在其他组的子节点处，那么从整个局势上看，最后要以祖宗划山头的，自己不是祖宗，自己要带着自己的子节点，全部投奔祖宗去。所以每次放到map中时，同样要寻根。才能放入。
最后要将拥有者加进去才符合输出的规范。
string find(string s, map<string, string> &p)//递归寻根 { return p[s] == s ? s : find(p[s], p); } vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) { map<string, string> owner; // map from the 邮箱 to 名字 map<string, string> parents; // map from an 邮箱 to its 邮箱的父亲 map<string, set<string>> unions; // the unions of accounts 并查集string下的结点们 for (int i = 0; i < accounts.size(); ++i) { //初始化 for (int j = 1; j < accounts[i].size(); ++j) { parents[accounts[i][j]] = accounts[i][j]; // 初始化自己是父亲 owner[accounts[i][j]] = accounts[i][0]; //保存一下每个邮箱的拥有者 } } for (int i = 0; i < accounts.size(); ++i) { // find and union 查找与合并 string ancestor = find(accounts[i][1], parents); for (int j = 2; j < accounts[i].size(); ++j) { parents[find(accounts[i][j], parents)] = ancestor; } } for (int i = 0; i < accounts.size(); ++i) { //将每个邮箱结点放入它的根节点带领的并查集中 for (int j = 1; j < accounts[i].size(); ++j) { unions[find(accounts[i][j], parents)].insert(accounts[i][j]); } } vector<vector<string>> res; map<string, set<string>>::iterator p=unions.begin(); for (;p!=unions.end();p++) { //取出每一个map对 vector<string> emails(p->second.begin(), p->second.end()); emails.insert(emails.begin(), owner[p->first]); //在emails.begin()前面插入owner[p.first]元素 res.push_back(emails); } return res; }
还有一种方案，就是将每组邮箱的行号作为父亲，这样更加简洁。
vector<int> f; vector<int> r; int findF(int x)//找父亲节点 { while (f[x] != x) x = f[x]; return x; } void merge(int x, int y)//合并，如果两个节点的祖宗相同，返回，如果不同，要归入一个祖宗门下 { int fx = findF(x); int fy = findF(y); if (fx == fy) return; if (r[fx] == r[fy]) r[fx]++; if (r[fx] > r[fy]) f[fy] = fx; else f[fx] = fy; } vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) { int n = accounts.size(); for (int i = 0; i < n; i++) { f.push_back(i);//初始化每组的父亲为行号 r.push_back(1); } map<string,int> m;//m 从邮箱到行号的映射 vector<vector<string>> ret; if (n == 0) return ret; for (int i = 1; i < accounts[0].size(); i++) { m[accounts[0][i]] = 0; } for (int i = 1; i < n; i++) { for (int j = 1; j < accounts[i].size(); j++) { if (m.find(accounts[i][j]) != m.end())//如果m中存在这个邮箱 { merge(m[accounts[i][j]], i); } else m[accounts[i][j]] = i;//如果不存在，插入 } } map<string,int>::iterator it; map<int, vector<string>> km; for (it = m.begin(); it != m.end(); it++) { int k = findF(it->second); if (km.find(k) == km.end()) km[k].push_back(accounts[k][0]); km[k].push_back(it->first); } map<int, vector<string>>::iterator it2; for (it2 = km.begin(); it2 != km.end(); it2++) { ret.push_back(it2->second); } return ret; }