C++在某个江湖中,相互认识的人会加入同一个门派,而互不认识的人不会加入相同的门派。若甲认识乙,且乙认识丙,那么甲和丙就算是认识的。对于给定的认识关系,请计算共有多少个门派,人数最多的门派有多少人。
时间: 2023-10-22 07:09:24 浏览: 208
一个免费的c++小游戏集合
5星 · 资源好评率100%
这是一个典型的并查集问题。我们可以用一个数组 `f` 来表示每个人所在的门派,初始时每个人的门派编号都为自己的编号,即 `f[i] = i`。然后,对于每一对认识关系 `(i, j)`,我们将它们所在的门派合并在一起,即令 `f[find(i)] = find(j)`,其中 `find(i)` 表示查找 `i` 所在的门派编号。
最终,门派的数量就等于门派编号为自己的数量,人数最多的门派就是门派中人数最多的那个。可以使用一个数组 `cnt` 来统计每个门派的人数,遍历所有人,将其所在门派的 `cnt` 值加1,然后再遍历一遍 `cnt` 数组,找到其中的最大值即可。
以下是 C++ 的示例代码:
```cpp
#include <iostream>
#include <vector>
using namespace std;
const int N = 1e5 + 10;
int n, m;
int f[N], cnt[N];
int find(int x) {
if (f[x] != x) f[x] = find(f[x]);
return f[x];
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; ++i) f[i] = i;
while (m--) {
int a, b;
cin >> a >> b;
f[find(a)] = find(b);
}
int ans = 0, max_cnt = 0;
for (int i = 1; i <= n; ++i) {
++cnt[find(i)];
}
for (int i = 1; i <= n; ++i) {
if (cnt[i] > 0) ++ans;
max_cnt = max(max_cnt, cnt[i]);
}
cout << ans << " " << max_cnt << endl;
return 0;
}
```
阅读全文