How Many Tables HDU - 1213 【并查集】

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1213

题意:求处理并查集后,树的个数

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

const int MAX_N = 2000+5;

int par[MAX_N];

void init() {
    for (int i = 1; i < MAX_N; ++i) {
        par[i] = i;
    }
    return;
}

int getPar(int x) {
    if (par[x] == x)  return x;
    else
    {
        return par[x] = getPar(par[x]);
    }
}

void UNION(int u, int v) {
    int x = getPar(u);
    int y = getPar(v);
    par[y] = x;
}

int main()
{
    int t;
    cin >> t;
    while (t--) {
        init();
        int n, m;
        cin >> n >> m;
        for (int i = 1; i <= m; i++) {
            int u, v;
            cin >> u >> v;
            UNION(u, v);
        }
        int res = 0;
        for (int i = 1; i <= n; i++) {
            if (par[i] == i) {
                ++res;
            }
        }
        cout << res << endl;

    }

    return 0;
}

 

全部评论

相关推荐

Southyeung:我说一下我的看法(有冒犯实属抱歉):(1)简历不太美观,给我一种看都不想看的感觉,感觉字体还是排版问题;(2)numpy就一个基础包,机器学习算法是什么鬼?我感觉你把svm那些写上去都要好一点。(2)课程不要写,没人看,换成获奖经历;(3)项目太少了,至少2-3个,是在不行把网上学习的也写上去。
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

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