基础算法合集-并查集
1.概念
并查集是一种树型的数据结构，用于处理一些不相交集合的合并及查询问题。 并查集的思想是用一个数组表示了整片森林（parent），树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里
2.如何实现
我推荐听这个视频(老师是边写代码,边画图), 讲起来很通俗, 画的图也很直观。 如果后续刷题的时候忘了就再看一遍,几分钟的视频也不会花费你很多时间。
进阶数据结构和算法-249-图-并查集-2_哔哩哔哩_bilibili
3.代码实现
核心代码部分
class DisjointSet{int[] s;public DisjointSet(int size){s=new int[size];for(int i=0;i<size;i++){s[i]=i;}public int find(int x){if(x==s[x]){return x;}return find(x);}public void union(int x,int y){s[y]=x;}}
}
public class Main {public static void main(String[] args) {DisjointSet set=new DisjointSet(7); }
}下面我们通过一道题来帮助你入门并查集
题目描述
给定一个列表 accounts，每个元素 accounts[i] 是一个字符串列表，其中第一个元素 accounts[i][0] 是 名称 (name) ，其余元素是 emails 表示该账户的邮箱地址。 现在，我们想合并这些账户。如果两个账户都有一些共同的邮箱地址，则两个账户必定属于同一个人。请注意，即使两个账户具有相同的名称，它们也可能属于不同的人，因为人们可能具有相同的名称。一个人最初可以拥有任意数量的账户，但其所有账户都具有相同的名称。 合并账户后，按以下格式返回账户：每个账户的第一个元素是名称，其余元素是 按字符 ASCII 顺序排列 的邮箱地址。账户本身可以以 任意顺序 返回。
原题链接: 721. 账户合并 - 力扣（LeetCode）
账户合并-代码实现(C++)
class DisjointSet{
public:vector<int> parent;DisjointSet(int n){parent.resize(n);for(int i=0;i<n;i++){parent[i]=i;}}int find(int x){if(parent[x]!=x){return find(parent[x]);}return parent[x];}void Union(int x,int y){parent[find(y)]=find(x);}
};
class Solution {
public:vector<vector<string>> accountsMerge(vector<vector<string>>& accounts) {int m=accounts.size();unordered_map<string,int> mp;DisjointSet uf(m);for(int i=0;i<m;i++){int n=accounts[i].size();for(int j=1;j<n;j++){string email=accounts[i][j];if(mp.count(email)==0){mp[email]=i;}else{uf.Union(i,mp[email]);}}}map<int,vector<string>> ms;for(auto& [email,idx]:mp){int fa=uf.find(idx);ms[fa].push_back(email);}vector<vector<string>> ans;for(auto& [idx,email]: ms){vector<string> userAccount;userAccount.push_back(accounts[idx][0]);vector<string> sortedEmail=email;sort(sortedEmail.begin(),sortedEmail.end());userAccount.insert(userAccount.end(),sortedEmail.begin(),sortedEmail.end());ans.push_back(userAccount);}return ans;}
};
/*
[["John", "johnsmith@mail.com", "john00@mail.com"],
["John", "johnnybravo@mail.com"],
["John", "johnsmith@mail.com", "john_newyork@mail.com"],
["Mary", "mary@mail.com"]][["John", 'john00@mail.com', 'john_newyork@mail.com', 'johnsmith@mail.com'],
["John", "johnnybravo@mail.com"],
["Mary", "mary@mail.com"]]
只要邮箱地址有相同的就能进行合并, 结果按任意顺序返回
*/账户合并-代码实现(Java)
class UnionFind {int[] parent;public UnionFind(int n) {parent = new int[n];for (int i = 0; i < n; i++) {parent[i] = i;}}public void union(int index1, int index2) {parent[find(index2)] = find(index1);}public int find(int index) {if (parent[index] != index) {parent[index] = find(parent[index]);}return parent[index];}
}
class Solution {public List<List<String>> accountsMerge(List<List<String>> accounts) {int m=accounts.size();Map<String,Integer> hm1=new HashMap<>(); UnionFind uf=new UnionFind(m);for(int i=0;i<m;i++){List<String> account=accounts.get(i);int n=account.size();for(int j=1;j<n;j++){String email=account.get(j);if(!hm1.containsKey(email)){hm1.put(email,i);}else{uf.union(i,hm1.get(email));}}}Map<Integer,List<String>> hm2=new TreeMap<>();for(Map.Entry<String,Integer> e: hm1.entrySet()){String email = e.getKey();int idx=e.getValue();int fa=uf.find(idx);if(!hm2.containsKey(fa)){hm2.put(fa,new ArrayList<String>());}hm2.get(fa).add(email);}List<List<String>> ans=new ArrayList<>();for(Map.Entry<Integer,List<String>> e:hm2.entrySet()){int idx=e.getKey();List<String> x=e.getValue();Collections.sort(x);List<String> tmp=new ArrayList<>();tmp.add(accounts.get(idx).get(0));tmp.addAll(x);ans.add(tmp);}return ans;}
}实现思路
解题思路的话,其实就是按题目模拟就行, 在阅读代码的时候, 可能会有的疑问我来解释一下
unordered_map<string,int> mp;它用来记录：
每个 邮箱地址 (
index)。
换句话说：
当我们在遍历每个账户的邮箱时，
- 如果某个邮箱第一次出现，就把它存进哈希表，并记录这个邮箱来自哪个账户（用
i表示账户下标）。 - 如果某个邮箱已经在哈希表里出现过了，说明当前账户和之前的那个账户是同一个人的（因为有相同邮箱），所以就用并查集合并它们。(合并账户)
举个例子帮助理解：
假如输入是：
accounts = [["John", "a@mail.com", "b@mail.com"],["Mary", "c@mail.com"],["John", "b@mail.com", "d@mail.com"]
]
| 步骤 | 遍历到的账户 | 邮箱 | emailToIndex 记录 | 并查集操作 |
| 1 | 账户0 ("John") | a@mail.com | a@mail.com -> 0 | 无 |
| 2 | 账户0 ("John") | b@mail.com | b@mail.com -> 0 | 无 |
| 3 | 账户1 ("Mary") | c@mail.com | c@mail.com -> 1 | 无 |
| 4 | 账户2 ("John") | b@mail.com | 已存在 -> 0 | 合并账户2和账户0 |
| 5 | 账户2 ("John") | d@mail.com | d@mail.com -> 2 | 无 |
作用总结一句话：
mp 用于快速判断邮箱是否出现过，并帮助找到它第一次出现的账户，从而用并查集把这些账户合并在一起，归属到同一个人。
map<int,vector> ms;
这个 map<int, vector<string>> ms 主要用于在合并完账户后，按照每个合并后的用户收集他们的所有邮箱地址作用：
它用来记录：
每个并查集的根节点（也就是合并后的“代表账户”的索引）对应的所有邮箱列表
为什么要用它？
因为同一个人可能有多个账户，这些账户通过相同的邮箱地址被并查集合并在了一起。
最后我们需要知道每个合并后的人的所有邮箱地址。
这时候：
ms 的 key 是并查集的根节点索引（代表这个人的账户索引）。
value 是这个人的所有邮箱地址的集合。结合例子来看：
比如这个例子：
accounts = [["John", "a@mail.com", "b@mail.com"],["Mary", "c@mail.com"],["John", "b@mail.com", "d@mail.com"]
]
经过并查集合并后：
- 账户 0 和 账户 2 是同一个人（因为都有 "b@mail.com"）。
- 账户 1 是 Mary。
那么 indexToEmails 大概是：
{0: ["a@mail.com", "b@mail.com", "d@mail.com"], // John1: ["c@mail.com"] // Mary
}
vector<vector> ans; (往ans里面填充答案即可)如何将vector<string> b, 追加到vector<string> a的结尾呢, 这里推荐使用insert这个成员函数
insert方法可以将一个容器的内容插入到另一个容器的指定位置。如果你想将`cnt`追加到`ans`的末尾，可以这样写：
ans.insert(ans.end(), cnt.begin(), cnt.end());
这里的ans.end()表示插入的位置是ans的末尾，cnt.begin()和cnt.end()分别表示要插入的内容的范围