- it技术
- 并查集
目录
并查集模板参考题目账户合并
并查集
模板
参考
并查集详解（超级简单有趣~~就学会了）
题目
账户合并
class Solution {
public List
<List
<String>> accountsMerge(List
<List
<String>> accounts
) {
DSU dsu
= new DSU();
Map
<String, String> emailToName
= new HashMap();
Map
<String, Integer> emailToID
= new HashMap();
int id
= 0;
for (List
<String> account
: accounts
) {
String name
= "";
for (String email
: account
) {
if (name
== "") {
name
= email
;
continue;
}
emailToName
.put(email
, name
);
if (!emailToID
.containsKey(email
)) {
emailToID
.put(email
, id
++);
}
dsu
.union(emailToID
.get(account
.get(1)), emailToID
.get(email
));
}
}
Map
<Integer
, List
<String>> ans
= new HashMap();
for (String email
: emailToName
.keySet()) {
int index
= dsu
.find(emailToID
.get(email
));
ans
.computeIfAbsent(index
, x
-> new ArrayList()).add(email
);
}
for (List
<String> component
: ans
.values()) {
Collections
.sort(component
);
component
.add(0, emailToName
.get(component
.get(0)));
}
return new ArrayList(ans
.values());
}
}
class DSU {
int[] parent
;
public DSU() {
parent
= new int[10001];
for (int i
= 0; i
<= 10000; ++i
)
parent
[i
] = i
;
}
public int find(int x
) {
if (parent
[x
] != x
) parent
[x
] = find(parent
[x
]);
return parent
[x
];
}
public void union(int x
, int y
) {
parent
[find(x
)] = find(y
);
}
}
