并查集
问题描述王希望一些男孩帮他做一个项目。因为这个项目相当复杂，<b>来的男孩越多越好</b>。当然也有一些要求<br><br>王先生选了一个足够大的房间来容纳孩子们。未被选中的男孩必须立即离开房间。房间里有10000000个男孩，一开始的数字从1到10000000。经过王先生的挑选，他们中任何两个仍然在这个房间里的人都应该是朋友（直接或间接），否则就只剩下一个男孩了。考虑到所有的直接朋友配对，你应该决定最好的方式<br>
输入
输入的第一行包含一个整数n（0≤n≤100 000）-直接朋友对的数量。下面的n行分别包含一对数字a和B，由一个空格分隔，这表明a和B是直接的朋友。（A≠B，1≤A，B≤10000000）
输出
一行中的输出正好包含一个整数，等于王可能保留的男孩的最大数量<br>
Sample Input
4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8
Sample Output
4
2
#include <stdio.h>
#include <stdlib.h>
#include "string.h"
long long int mer={0},max={0};
long long int i,a,b,imax;
long long int n;
long long int find(long long int x)
{
if(x!=mer)
{
mer=find(mer);
}
max]++;
if(max]>imax) imax=max];
return mer;
}
void merge(long long int x,long long int y)
{
long long int fx,fy;
fx=find(x);
fy=find(y);
if(fx!=fy)
{
mer=fy;
}
}
int main()
{
while(scanf("%lld",&n)!=EOF)
{
memset(max,0,sizeof(max));
imax=0;
for(i=1;i<=10000001;i++)
{
mer=i;
}
while(n--)
{
scanf("%lld%lld",&a,&b);
merge(a,b);
}
printf("%lld\n",imax+1);
}
return 0;
}
提示我内存超了，请问应该怎么优化{:10_286:} 你的存储数组 mer 和 max 的大小为 10000002，而题目中男孩的编号仅有 10000000，并且每个男孩只会被遍历一次，因此你可以将数组大小改为 10000001。
同时，如果在参数范围内存在多组数据，你应该在每组数据前清空 mer 和 max 数组，而不是把它们声明成全局变量并只在第一组数据前清空。
根据提示信息，你的程序存在内存超限的情况。可以考虑减少对数组的使用。
可以将max数组和mer数组合并，在find函数返回之前记录相关值，这样就没有必要再遍历一遍max数组了。同时，也可以将合并操作优化为按秩合并。
下面是优化后的代码：
#include <stdio.h>
#include <stdlib.h>
#include "string.h"
#define MAXN 10000001
long long int fa, rank, cnt;
long long int find(long long int x) {
if (fa != x) {
return fa = find(fa);
}
return x;
}
void merge(long long int x,long long int y)
{
long long int fx, fy;
fx = find(x);
fy = find(y);
if (fx != fy) {
if (rank > rank) {
fa = fx;
cnt += cnt;
} else {
fa = fy;
cnt += cnt;
if (rank == rank) {
rank++;
}
}
}
}
int main() {
long long int n, a, b;
while(scanf("%lld", &n) != EOF) {
for (long long int i = 1; i <= MAXN; i++) {
fa = i;
rank = 0;
cnt = 1;
}
while(n--) {
scanf("%lld %lld", &a, &b);
merge(a, b);
}
long long max_cnt = 0;
for (long long int i = 1; i <= MAXN; i++) {
if (fa == i && cnt > max_cnt) {
max_cnt = cnt;
}
}
printf("%lld\n", max_cnt);
}
return 0;
}
有用请设置最佳答案{:10_254:} sfqxx 发表于 2023-5-27 21:47
根据提示信息，你的程序存在内存超限的情况。可以考虑减少对数组的使用。
可以将max数组和mer数组合并， ...
还是太大.... 萨西摩尔·槿花 发表于 2023-5-27 21:55
还是太大....
可以考虑优化存储策略，使用一个二维数组来存储朋友对的关系，如`bool friend`，用 friend 表示编号为 i 和 j 的男孩是否为朋友。然后再用并查集来处理朋友之间的关系，这样就可以节省掉并查集中的 cnt 数组和 rank 数组了。具体实现时可以将每个男孩看作并查集中的一个节点，当输入直接朋友对时，将对应的节点合并到同一集合中。最后，可以统计并查集中每个集合的大小，找到最大值即可。
另外，还可以考虑使用按需分配的方式来代替全局声明的数组，以便节省内存。对于这个问题，可以使用 C++ 的 STL 容器 `vector` 来保存邻接矩阵`friend`以及并查集数组`fa`。
页:
[1]