Java教程

基础算法 836.合并集合

本文主要是介绍基础算法 836.合并集合，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

并查集，使用数组实现，find函数中使用了巧妙的递归

#include<iostream>
using namespace std;

const int N = 100010;
int p[N];

int find(int k){
    if(p[k] != k) p[k] = find(p[k]);
    return p[k];
}

int main(){
    int m,n;
    scanf("%d%d",&m,&n);
    for(int i = 1; i <= m; i++) p[i] = i;
    while(n --){
        char t[2];
        int a, b;
        scanf("%s%d%d",t,&a,&b);
        if(*t == 'M')p[find(a)] = find(b);
        else {
            if(find(a) == find(b)) puts("Yes");
            else puts("No");
        }
    }
    return 0;
}

　　

这篇关于基础算法 836.合并集合的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航