并查集

萨西摩尔·槿花

问题描述
王希望一些男孩帮他做一个项目。因为这个项目相当复杂，<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

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include "string.h"
   
4. 
   
5. long long int mer[10000002]={0},max[10000002]={0};
   
6. long long int i,a,b,imax;
   
7. long long int n;
   
8. 
   
9. long long int find(long long int x)       
   
10. {
    
11.         if(x!=mer[x])
    
12.         {
    
13.                 mer[x]=find(mer[x]);
    
14.         }
    
15.         max[mer[x]]++;
    
16.         if(max[mer[x]]>imax) imax=max[mer[x]];
    
17.         return mer[x];
    
18. }
    
19. 
    
20. void merge(long long int x,long long int y)
    
21. {
    
22.         long long int fx,fy;
    
23.         fx=find(x);
    
24.         fy=find(y);
    
25.         if(fx!=fy)
    
26.         {
    
27.                 mer[fx]=fy;
    
28.         }
    
29. }
    
30. 
    
31. int main()
    
32. {
    
33.     while(scanf("%lld",&n)!=EOF)
    
34.     {
    
35.             memset(max,0,sizeof(max));
    
36.             imax=0;
    
37.             for(i=1;i<=10000001;i++)
    
38.             {
    
39.                     mer[i]=i;
    
40.                 }
    
41.                    while(n--)        
    
42.                 {
    
43.                         scanf("%lld%lld",&a,&b);
    
44.                         merge(a,b);
    
45.                 }
    
46.                 printf("%lld\n",imax+1);
    
47.         }
    
48.        
    
49.        
    
50.     return 0;
    
51. }
    

复制代码

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

陶远航

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

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

sfqxx

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

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

下面是优化后的代码：

1. #include <stdio.h>
   
2. #include <stdlib.h>
   
3. #include "string.h"
   
4. 
   
5. #define MAXN 10000001
   
6. 
   
7. long long int fa[MAXN], rank[MAXN], cnt[MAXN];
   
8. 
   
9. long long int find(long long int x) {
   
10.     if (fa[x] != x) {
    
11.         return fa[x] = find(fa[x]);
    
12.     }
    
13.     return x;
    
14. }
    
15. 
    
16. void merge(long long int x,long long int y)
    
17. {
    
18.     long long int fx, fy;
    
19.     fx = find(x);
    
20.     fy = find(y);
    
21.     if (fx != fy) {
    
22.         if (rank[fx] > rank[fy]) {
    
23.             fa[fy] = fx;
    
24.             cnt[fx] += cnt[fy];
    
25.         } else {
    
26.             fa[fx] = fy;
    
27.             cnt[fy] += cnt[fx];
    
28.             if (rank[fx] == rank[fy]) {
    
29.                 rank[fy]++;
    
30.             }
    
31.         }
    
32.     }
    
33. }
    
34. 
    
35. int main() {
    
36.     long long int n, a, b;
    
37.     while(scanf("%lld", &n) != EOF) {
    
38.         for (long long int i = 1; i <= MAXN; i++) {
    
39.             fa[i] = i;
    
40.             rank[i] = 0;
    
41.             cnt[i] = 1;
    
42.         }
    
43.         while(n--) {
    
44.             scanf("%lld %lld", &a, &b);
    
45.             merge(a, b);
    
46.         }
    
47.         long long max_cnt = 0;
    
48.         for (long long int i = 1; i <= MAXN; i++) {
    
49.             if (fa[i] == i && cnt[i] > max_cnt) {
    
50.                 max_cnt = cnt[i];
    
51.             }
    
52.         }
    
53.         printf("%lld\n", max_cnt);
    
54.     }
    
55.     return 0;
    
56. }

复制代码

有用请设置最佳答案

萨西摩尔·槿花

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`。