看到要将一堆人联系起来,本蒟蒻第一时间想到的就是并查集,但是这里要我们输出的是最大群体。我们知道并查集路径压缩后每次查找这个群体的时候都会返回他们的“”祖宗“”,所以我们将群体的大小保存在“”祖宗“”里面,这样当两个群体合并的时候只需要将“”祖宗“”里面的数加到另外一个群体的‘’祖宗‘’就好了
AC代码:
#include<bits/stdc++.h> using namespace std; int flag[100005]; int sum[100005]; int find(int x) { if(x!=flag[x]) { flag[x]=find(flag[x]); } return flag[x]; } void marge(int x,int y) { int a=find(x);//找祖宗 int b=find(y);//找祖宗 if(a!=b) { flag[b]=a;//y的祖宗认x的祖宗为祖宗 sum[a]+=sum[b];//将y的祖宗的人数加到x的祖宗里面 } } int main() { int n; while(~(scanf("%d",&n))) { for(int i=1;i<=100000;i++) { flag[i]=i;//一开始祖宗就是自己 sum[i]=1;//一开始每个人都是为1的群体 } while(n--) { int x,y; scanf("%d%d",&x,&y); marge(x,y); } int maxn=0; for(int i=1;i<100000;i++)//找最大的群体 { maxn=max(maxn,sum[i]); } printf("%d\n",maxn); } return 0; }
0.0分
0 人评分
C语言训练-计算1977!* (C语言代码)浏览:899 |
C二级辅导-进制转换 (C语言代码)浏览:514 |
2003年秋浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:698 |
蓝桥杯历届试题-九宫重排 (C++代码)浏览:2783 |
【明明的随机数】 (C++代码)浏览:781 |
C语言训练-阶乘和数* (C语言代码)-------- 呆板写法浏览:1362 |
WU-复数求和 (C++代码)浏览:2015 |
C语言程序设计教程(第三版)课后习题8.8 (C语言代码)浏览:642 |
蛇行矩阵 (C语言代码)浏览:536 |
矩阵加法 (C语言代码)浏览:1723 |