朋友圈

某学校有 N 个学生，形成 M 个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据 “我的朋友的朋友也是我的朋友” 这个推论可以得出，如果 A 和 B 是朋友，且 B 和 C 是朋友，则 A 和 C 也是朋友。请编写程序计算最大朋友圈中有多少人。

输入格式

输入的第一行包含两个正整数 N（≤30000）和 M（≤1000），分别代表学校的学生总数和俱乐部的个数。后面的 M 行每行按以下格式给出 1 个俱乐部的信息，其中学生从 1~N 编号：

第 i 个俱乐部的人数 Mi（空格）学生 1（空格）学生 2 … 学生 Mi

输出格式

输出给出一个整数，表示在最大朋友圈中有多少人。

输入样例

1
2
3
4
5

7 4
3 1 2 3
2 1 4
3 5 6 7
1 6

输出样例

1

4

一些限制

解题思路

1. 初始化 init

   1 2 3 4 5

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

2. 查询 find

   1 2 3 4 5 6 7

   int find(int i) { if(i == fa[i]) return i; else { fa[i] = find(fa[i]); return fa[i]; } }

3. 合并 unionn

   1 2 3 4

   void union1(int a, int b) { int afa = find(a), bfa = find(b); fa[afa] = bfa; }

4. 更新 update（这个是我写题时想到的）

   1 2 3 4 5 6 7

   int update(int i) { if(i == fa[i]) return i; else { fa[i] = find(fa[i]); return fa[i]; } }

5. 最后的数据整理工作（如统计最大的人数等）

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

   unordered_map<int, int> mp; for(int i = 1; i <= N; ++i) { update(i); } for(int i = 1; i <= N; ++i) { if(mp.find(fa[i]) != mp.end()) { mp[fa[i]] += 1; } else { mp[fa[i]] = 1; } } for(auto i: mp) { maxCount = max(maxCount, i.second); } cout << maxCount;

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

#include <bits/stdc++.h>
using namespace std;
int fa[30020];

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

int find(int i) {
	if(i == fa[i]) return i;
	else {
		fa[i] = find(fa[i]);
		return fa[i];
	}
}

int update(int i) {
	if(i == fa[i]) return i;
	else {
		fa[i] = find(fa[i]);
		return fa[i];
	}
}

void union1(int a, int b) {
	int afa = find(a), bfa = find(b);
	fa[afa] = bfa;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	int N, M, Mi, maxCount = 0;
	cin >> N >> M;
	init(N);
	for(int i = 1; i <= M; ++i) {
        int a, b;
		cin >> Mi >> a;
		for(int j = 1; j <= Mi-1; ++j) {
			cin >> b;
		    union1(a, b);
            a = b;
		}
	}
    for(int i = 1; i <= N; ++i) {
		update(i);
	}
    unordered_map<int, int> mp;
	for(int i = 1; i <= N; ++i) {
        if(mp.find(fa[i]) != mp.end()) {
            mp[fa[i]] += 1;
        } else {
            mp[fa[i]] = 1;
        }
    }
    for(auto i: mp) {
        maxCount = max(maxCount, i.second);
    }
	cout << maxCount;
}