首页 > 编程语言 > 详细

基础算法学习--并查集

时间:2021-04-20 23:10:13      阅读:20      评论:0      收藏:0      [点我收藏+]

并查集模板

//查找并返回根节点
int find(int x){
    if(p[x] != x) p[x] = find(p[x]);    //若不是根节点的话就调用find函数查找上一个节点,并在结束时压缩路径优化
    return p[x];    //返回根节点编号
}

int main(){
    for(int i = 1;i <= n;i ++) p[i] = i;    //将所有的根节点从1开始递增编号初始化
}

例题

题目

合并集合

代码

#include<iostream>

using namespace std;

const int N = 100010;

int n,m;
int p[N];   //父节点数组

//返回x对应的根节点编号
int find(int x){
    if(p[x] != x) p[x] = find(p[x]);
    return p[x];
}

int main(){
    cin >> n >> m;
    
    //初始化所有的根节点编号
    for(int i = 1;i <= n;i ++) p[i] = i;
    
    while(m --){
        char op[2];
        int a,b;
        
        scanf("%s%d%d",op,&a,&b);
        
        //将a所在的整个集合插入b所在的集合中
        if(op[0] == ‘M‘) p[find(a)] = find(b);
        else cout << (find(a) == find(b) ? "Yes" : "No") << endl;
    }
    
    return 0;
}

基础算法学习--并查集

原文:https://www.cnblogs.com/Xuuxxi/p/14682995.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!