并查集 ---- 啊哈算法

举报
楚楚冻人玥玥仙女 发表于 2021/11/19 02:42:07 2021/11/19
1.2k+ 0 0
【摘要】 // // Created by jal on 18-9-3. // #include <bits/stdc++.h> using namespace std; const int MAXN...
//
// Created by jal on 18-9-3.
//

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100;
int n,m;
int F[MAXN];

int father(int u){
    return F[u] == u ? u : F[u] = father(F[u]);
}
void merge(int u, int v){
    int root_u = father(u);
    int root_v = father(v);
    if(root_u != root_v){
        F[root_u] = root_v;
    }
}
int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        F[i] = i;
    }
    for(int i = 1; i <= m; i++){
        int x,y,z;
        cin >> x >> y;
        merge(x,y);
    }
    int cnt = 0;
    for(int i = 1; i <= n; i++){
        if(F[i] == i){
            cnt++;
        }
    }
    cout << cnt << endl;
}

/*
 input:

 10 9
 1 2
 3 4
 5 2
 4 6
 2 6
 8 7
 9 7
 1 6
 2 4

 output:

 3
 */
  
 

文章来源: blog.csdn.net,作者:爱玲姐姐,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/jal517486222/article/details/82347698

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

作者其他文章

评论(0

抱歉,系统识别当前为高风险访问,暂不支持该操作

    全部回复

    上滑加载中

    设置昵称

    在此一键设置昵称,即可参与社区互动!

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

    *长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。