POJ1611

计算被感染人的数量，开一个数组记录数量，水题。

#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 30005;

int f[N], num[N], arr[N];
int n, m;

void init() {
    for (int i = 0; i < n; i++) {
        f[i] = i;
        num[i] = 1;
    }
}

int find(int x) {
    return x == f[x] ? x : f[x] = find(f[x]);
}

void Union(int a, int b) {
    int pa = find(a);
    int pb = find(b);
    if (pa != pb) {
        if (num[pa] >= num[pb]) {
            f[pb] = pa;
            num[pa] += num[pb];
        }
        else {
            f[pa] = pb;
            num[pb] += num[pa];
        }
    }
}

int main() {
    while (scanf("%d %d", &n, &m) && (n || m)) {
        int k;
        init();
        while (m--) {
            scanf("%d", &k);
            for (int i = 0; i < k; i++)  
                scanf("%d", &arr[i]);
            for (int i = 1; i < k; i++)
                Union(arr[0], arr[i]);
        }
        int p = find(0);
        printf("%dn", num[p]);
    }
    return 0;
}

最后

以上就是瘦瘦微笑为你收集整理的POJ1611的全部内容，希望文章能够帮你解决POJ1611所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。