721. 账户合并
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name)，其余元素是 emails 表示该帐户的邮箱地址。
现在，我们想合并这些帐户。如果两个帐户都有一些共同的邮件地址，则两个帐户必定属于同一个人。请注意，即使两个帐户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的帐户，但其所有帐户都具有相同的名称。
合并帐户后，按以下格式返回帐户：每个帐户的第一个元素是名称，其余元素是按顺序排列的邮箱地址。accounts 本身可以以任意顺序返回。
例子 1:
Input:
accounts = [["John", "[email protected]", "[email protected]"], ["John", "[email protected]"], ["John", "[email protected]", "[email protected]"], ["Mary", "[email protected]"]]
Output: [["John", '[email protected]', '[email protected]', '[email protected]'], ["John", "[email protected]"], ["Mary", "[email protected]"]]
Explanation:
第一个和第三个 John 是同一个人，因为他们有共同的电子邮件 "[email protected]"。
第二个 John 和 Mary 是不同的人，因为他们的电子邮件地址没有被其他帐户使用。
我们可以以任何顺序返回这些列表，例如答案[['Mary'，'[email protected]']，['John'，'[email protected]']，
['John'，'[email protected]'，'[email protected]'，'[email protected]']]仍然会被接受。
注意：
accounts的长度将在[1，1000]的范围内。
accounts[i]的长度将在[1，10]的范围内。
accounts[i][j]的长度将在[1，30]的范围内。
PS：
并查集，先找到每一个邮件的父级，就是最顶层的那个并查集，
然后在手动循环一遍，找到所有的父级
然后在把他父级的名称拿过来（找最原来的list的第一个字符串，就是他的名字）
这里
lll.add(accounts.get(e.getValue()).get(0));
e.getValue就是我当时放入的f[i]，就是最顶层的下标，然后再找名字
后面就…………就可以了，（小编表达能力比较差，有不清楚的欢迎评论）
class Solution {
public static int [] f = new int[1010];
public static void changeFather(int a,int b){
int a_ = find(a);
int b_ = find(b);
if(a_==b_)
return;
//赋值的时候也是把旧的赋值给新的
f[b_]= a_;
}
public static int find(int x){
while(x!=f[x]){
x = f[x];
}
return x;
}
public List<List<String>> accountsMerge(List<List<String>> accounts) {
int len = accounts.size();
for (int i = 0; i < 1010; i++) {
f[i]=i;
}
HashMap<String ,Integer> m = new HashMap<>();
for (int i = 0; i <len; i++) {
List<String> list = accounts.get(i);
for (int j = 1; j < accounts.get(i).size(); j++) {
if(m.containsKey(list.get(j))){
//查找(左面是旧的右面是新的)
changeFather(m.get(list.get(j)),i);
}
else{
//没有就给他当前的
m.put(list.get(j),f[i]);
}
}
}
//在循环一遍，找到所有的父级
//key是邮箱，value是他的父级
for(Map.Entry<String ,Integer> s:m.entrySet()){
s.setValue(find(s.getValue()));
}
Map<Integer,List<String>> mm = new HashMap<>();
for (Map.Entry<String,Integer> e:m.entrySet()) {
if(!mm.containsKey(e.getValue())){
List<String> lll = new ArrayList<>();
//把他父级的对应的名称拿过来
lll.add(accounts.get(e.getValue()).get(0));
mm.put(e.getValue(),lll);
}
//如果有名字了，直接添加
mm.get(e.getValue()).add(e.getKey());
}
//把最后的结果加起来
List<List<String>> ans = new LinkedList<>();
for (Map.Entry<Integer,List<String>> e:mm.entrySet()) {
List<String> lt = e.getValue();
Collections.sort(lt);
ans.add(lt);
}
return ans;
}
}