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;
}
全部评论

相关推荐

不愿透露姓名的神秘牛友
07-04 14:35
点赞 评论 收藏
分享
Lorn的意义:你这种岗位在中国现在要么牛马天天加班,要么关系户进去好吃好喝,8年时间,真的天翻地覆了,对于资本来说你就说一头体力更好的牛马,哎,退伍没有包分配你真的亏了。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务