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

相关推荐

码农索隆:想看offer细节
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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