2024-12-25 15:49 门头沟学院 C++ 发布于江西
关注
day56
并查集模板：
//把并查集的模板函数写好，后面直接调用即可
int n;//结点数量（n取题目给出的最大值+1）
vector<int> father = vector<int>(n, 0);
//初始化
void init(){
for(int i = 0; i < n; i++){
father[i] = i;//根节点都初始化为自己
}
}
//寻根
int find(int u){
return u == father[u] ? u : father[u] = find(father[u]);//路径压缩
}
//判断是否为同一个根
bool isSame(int u, int v){
u = find(u);
v = find(v);//这样寻根的同时，也在进行路径压缩
return u == v;
}
//将两个元素加入一个集合
void join(int u, int v){
u = find(u);
v = find(v);
if(u == v) return;
father[v] = u;
}
//把并查集的模板函数写好，后面直接调用即可
int n;//结点数量（n取题目给出的最大值+1）
vector<int> father = vector<int>(n, 0);
//初始化
void init(){
for(int i = 0; i < n; i++){
father[i] = i;//根节点都初始化为自己
}
}
//寻根
int find(int u){
return u == father[u] ? u : father[u] = find(father[u]);//路径压缩
}
//判断是否为同一个根
bool isSame(int u, int v){
u = find(u);
v = find(v);//这样寻根的同时，也在进行路径压缩
return u == v;
}
//将两个元素加入一个集合
void join(int u, int v){
u = find(u);
v = find(v);
if(u == v) return;
father[v] = u;
}
全部评论
相关推荐
查看14道真题和解析
不愿透露姓名的神秘牛友
08-08 18:20
职场水母：这题思路是什么，我目前想的一个暴力方法就是先把这个链表遍历一遍，用哈希表存储出现次数，然后再根据哈希表来一个一个删除节点， 点赞 评论 收藏
分享
