11633: 【原1633】African

题目描述

author: TA 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/1633

Description

黑助教由于外号不吉利的缘故导致脸一直都很黑，被助教组公认为非洲酋长。众所周知，非洲人是一种极易传染的体质，如果经常在一起谈笑风生的一群助教中有一个或以上的非洲人，那么这一群助教都会变成非洲人。某日方神欲氪一单648补全图鉴（剧情需要，请勿模仿），但又怕已经被小黑传染，成了非洲人，于是他求助于你。方神会告诉你助教组的总人数n和助教组中小团体的个数m（小团体中的助教会经常一起谈笑风生，一位助教可以在零个或多个多个小团体内），请你告诉方神助教组中已经有多少个非洲人了。假设一开始只有小黑一个非洲人。

Input Format

第一行两个整数n, m，表示助教组中有n位助教，m个小团体。接下来m行，每行开始一个数k，表示该小团体中共有k位助教经常一起谈笑风生，接下来k个0到n-1之间的整数，表示该小团体内的助教。注意黑助教永远是0号。

Output Format

一个整数，表示助教组中的非洲人的个数。

Sample Input

100 4 
2 1 2 
5 10 13 11 12 14 
2 0 1 
2 99 2

Sample Output

数据范围

对于40%的数据，n <= 100, m <= 10；
对于100%的数据，n <= 30000, m <= 500。

BugenZhao's solution

//
// Created by BugenZhao on 2019/5/19.
//

#include <iostream>
#include <string>

using std::ios, std::cin, std::cout, std::endl, std::string;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;

    int *id = new int[n];
    int *sz = new int[n];
    int count = n;
    for (int i = 0; i < n; ++i) {
        id[i] = i, sz[i] = 1;
    }

    auto find = [&](int p) {
        while (p != id[p]) p = id[p];
        return p;
    };

    auto uni = [&](int p, int q) {
        int pr = find(p);
        int qr = find(q);
        if (pr == qr) return;
        if (sz[pr] < sz[qr]) {
            id[pr] = qr;
            sz[qr] += sz[pr];
        } else {
            id[qr] = pr;
            sz[pr] += sz[qr];
        }
        --count;
    };

    while (m--) {
        int k, root, tmp;
        cin >> k >> root;
        for (int i = 0; i < k - 1; ++i) {
            cin >> tmp;
            uni(tmp, root);
        }
    }

    int id0 = find(0);
    int ans = 0;
    for (int i = 0; i < n; ++i) {
        if (find(i) == id0) ++ans;
    }

    cout << ans << endl;
    delete[] id;
    delete[] sz;
    return 0;
}

ligongzzz's solution

#include <iostream>
#include <cstring>
using namespace std;

class dset {
public:
    int set_data[30009] = { 0 };
    dset() {
        memset(set_data, -1, sizeof(set_data));
    }
    void set_union(int root1, int root2) {
        if (root1 == root2)
            return;
        if (set_data[root1] < set_data[root2]) {
            set_data[root1] += set_data[root2];
            set_data[root2] = root1;
        }
        else {
            set_data[root2] += set_data[root1];
            set_data[root1] = root2;
        }
    }
    int set_find(int pos) {
        if (set_data[pos] < 0)
            return pos;
        return set_data[pos] = set_find(set_data[pos]);
    }
};

dset set_data;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m;
    cin >> n >> m;

    for (; m > 0; --m) {
        int k;
        cin >> k;
        int temp;
        cin >> temp;
        for (; k > 1; --k) {
            int i;
            cin >> i;
            set_data.set_union(set_data.set_find(temp), set_data.set_find(i));
        }
    }

    cout << -set_data.set_data[set_data.set_find(0)];

    return 0;
}

skyzh's solution

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;

const int MAX_CONNECTION = 30001;
int link[MAX_CONNECTION];

int parent(int x) {
    if (link[x] == x) return x;
    return link[x] = parent(link[x]);
}

int make_link(int i, int j) {
    int a = parent(i), b = parent(j);
    link[a] = b;
}

int main() {
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; i++) link[i] = i;
    for (int i = 0; i < m; i++) {
        int t;
        int op1, op2;
        scanf("%d%d", &t, &op1);
        for (int j = 1; j < t; j++) {
            scanf("%d", &op2);
            make_link(op1, op2);
        }
    }
    int cnt = 0;
    for (int i = 0; i < n; i++) {
        if (parent(0) == parent(i)) cnt++;
    }
    cout << cnt << endl;
    return 0;
}