C++代码实现 小计是一个程序员,他为学校做了一个校园聊天系统,已知系统中有 n 名用户,编号为 1~n,现在已知有 m 对好友关系,每一对关系由两个整数 x 和 y 组成 ,表示编号为 x 的用户和编号为 y 的用户是一对好友,请问校园中有多少个圈子,人数最多的圈子有多少人。 圈子:一个圈子中的人一定直接与同圈子的其他人是好友,或者通过若干名同圈子的人,间接与同圈子的其他人是好友。 小计是一个程序员,他为学校做了一个校园聊天系统,已知系统中有 n 名用户,编号为 1~n,现在已知有 m 对好友关系,每一对关系由两个整数 x 和 y 组成 ,表示编号为 x 的用户和编号为 y 的用户是一对好友,请问校园中有多少个圈子,人数最多的圈子有多少人。 圈子:一个圈子中的人一定直接与同圈子的其他人是好友,或者通过若干名同圈子的人,间接与同圈子的其他人是好友。
时间: 2023-11-27 20:55:29 浏览: 53
以下是 C++ 代码实现:
```cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n, m;
int parent[MAXN], cnt[MAXN];
int find(int x) {
if (x != parent[x]) {
parent[x] = find(parent[x]);
}
return parent[x];
}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (x != y) {
parent[x] = y;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
parent[i] = i;
cnt[i] = 1;
}
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
unite(x, y);
}
int ans = 0, maxCnt = 0;
for (int i = 1; i <= n; i++) {
int root = find(i);
cnt[root]++;
if (root == i) {
ans++;
maxCnt = max(maxCnt, cnt[root]);
}
}
cout << ans << " " << maxCnt << endl;
return 0;
}
```
在这个算法中,我们首先初始化每个节点的父节点为它本身,并初始化每个节点所属的圈子大小为 1。然后我们遍历每一对好友关系,将两个人所在的圈子合并。最后,我们遍历每个节点,找到它所属的圈子的根节点,并将该圈子的大小加一。如果该节点是根节点,那么意味着它所属的圈子是一个新的圈子,此时将答案加一,并且更新最大圈子大小。最后输出答案即可。
时间复杂度为 $O(m \log n)$,其中 $m$ 是好友关系的数量,$n$ 是节点的数量。