首页 > 其他 > 详细

洛谷P1536 村村通 题解 并查集

时间:2020-02-16 23:01:50      阅读:47      评论:0      收藏:0      [点我收藏+]

题目链接:https://www.luogu.com.cn/problem/P1536

题目大意:告诉你一些点属于同一个集合,求最少连多少条边能够合成一个集合。

解题思路:

最少连边数 = 集合数 - 1。

实现代码如下:

#include<bits/stdc++.h>
using namespace std;
const int maxn = 10010;
int n, m, f[maxn], cnt;
bool vis[maxn];
int func_find(int x) {
    return x == f[x] ? x : f[x] = func_find(f[x]);
}
int func_union(int x, int y) {
    int a = func_find(x), b = func_find(y);
    f[a] = f[b] = f[x] = f[y] = min(a, b);
}
void init() {
    for (int i = 1; i <= n; i ++) f[i] = i;
    for (int i = 1; i <= n; i ++) vis[i] = false;
    cnt = 0;
}
int main() {
    while (cin >> n) {
        if (n == 0) break;
        cin >> m;
        init();
        while (m --) {
            int x, y;
            cin >> x >> y;
            func_union(x, y);
        }
        for (int i = 1; i <= n; i ++) {
            int rt = func_find(i);
            if (!vis[rt]) {
                vis[rt] = true;
                cnt ++;
            }
        }
        cout << cnt-1 << endl;
    }
    return 0;
}

洛谷P1536 村村通 题解 并查集

原文:https://www.cnblogs.com/quanjun/p/12319082.html

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