# 11633: 【原1633】African

### 题目描述

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

## Sample Input

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

## Sample Output

``````4
``````

## 数据范围

• 对于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 parent(int x) {
if (link[x] == x) return x;
}

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

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);