并查集

萨西摩尔·槿花

问题描述
王希望一些男孩帮他做一个项目。因为这个项目相当复杂，<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[10000002]={0},max[10000002]={0};
long long int i,a,b,imax;
long long int n;

long long int find(long long int x)        
{
        if(x!=mer[x])
        {
                mer[x]=find(mer[x]);
        }
        max[mer[x]]++;
        if(max[mer[x]]>imax) imax=max[mer[x]];
        return mer[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)
        {
                mer[fx]=fy;
        }
}

int main()
{
    while(scanf("%lld",&n)!=EOF)
    {
            memset(max,0,sizeof(max));
            imax=0;
            for(i=1;i<=10000001;i++)
            {
                    mer[i]=i;
                }
                   while(n--)         
                {
                        scanf("%lld%lld",&a,&b);
                        merge(a,b);
                }
                printf("%lld\n",imax+1); 
        }
        
        
    return 0;
}
 

提示我内存超了，请问应该怎么优化

陶远航

你的存储数组 mer 和 max 的大小为 10000002，而题目中男孩的编号仅有 10000000，并且每个男孩只会被遍历一次，因此你可以将数组大小改为 10000001。

同时，如果在参数范围内存在多组数据，你应该在每组数据前清空 mer 和 max 数组，而不是把它们声明成全局变量并只在第一组数据前清空。

sfqxx

根据提示信息，你的程序存在内存超限的情况。可以考虑减少对数组的使用。

可以将max数组和mer数组合并，在find函数返回之前记录相关值，这样就没有必要再遍历一遍max数组了。同时，也可以将合并操作优化为按秩合并。

下面是优化后的代码：

#include <stdio.h>
#include <stdlib.h>
#include "string.h"

#define MAXN 10000001

long long int fa[MAXN], rank[MAXN], cnt[MAXN];

long long int find(long long int x) {
    if (fa[x] != x) {
        return fa[x] = find(fa[x]);
    }
    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[fx] > rank[fy]) {
            fa[fy] = fx;
            cnt[fx] += cnt[fy];
        } else {
            fa[fx] = fy;
            cnt[fy] += cnt[fx];
            if (rank[fx] == rank[fy]) {
                rank[fy]++;
            }
        }
    }
}

int main() {
    long long int n, a, b;
    while(scanf("%lld", &n) != EOF) {
        for (long long int i = 1; i <= MAXN; i++) {
            fa[i] = i;
            rank[i] = 0;
            cnt[i] = 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] == i && cnt[i] > max_cnt) {
                max_cnt = cnt[i];
            }
        }
        printf("%lld\n", max_cnt);
    }
    return 0;
}

有用请设置最佳答案

萨西摩尔·槿花

sfqxx 发表于 2023-5-27 21:47
根据提示信息，你的程序存在内存超限的情况。可以考虑减少对数组的使用。

可以将max数组和mer数组合并， ...

还是太大....

sfqxx

萨西摩尔·槿花 发表于 2023-5-27 21:55
还是太大....

可以考虑优化存储策略，使用一个二维数组来存储朋友对的关系，如`bool friend[MAXN][MAXN]`，用 friend[i ][j] 表示编号为 i 和 j 的男孩是否为朋友。然后再用并查集来处理朋友之间的关系，这样就可以节省掉并查集中的 cnt 数组和 rank 数组了。具体实现时可以将每个男孩看作并查集中的一个节点，当输入直接朋友对时，将对应的节点合并到同一集合中。最后，可以统计并查集中每个集合的大小，找到最大值即可。

另外，还可以考虑使用按需分配的方式来代替全局声明的数组，以便节省内存。对于这个问题，可以使用 C++ 的 STL 容器 `vector` 来保存邻接矩阵`friend`以及并查集数组`fa`。