uva 10608 FRIENDS

纯粹考察并查集，算是一个经典问题；统计一个集合中有多少个元素，然后找到元素个数最多的集合

就普通的并查集，就能过了

然后另外写了压缩路径，没想到时间没有改变

然后再写一个，时间还是没有改变，好吧……………………

只要懂基本的并查集的话，代码都不成问题，很裸的并查集而已

 

代码一：纯粹

#include <cstdio> #include <cstring> #define N 30000 int p[N],c[N]; int n,m;int find(int x) { return p[x]==x ? x : p[x]=find(p[x]); }int main() {int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1; i<=n; i++){ p[i]=i; c[i]=0; }for(int i=1; i<=m; i++){int x,y,u,v;scanf("%d%d",&u,&v);x=find(u);y=find(v);if(x!=y)p[x]=y;}for(int i=1; i<=n; i++) //扫描所有元素找到他们的祖先然后祖先的孩子数计数 {int x=find(i);c[x]++;}int max=0;for(int i=1; i<=n; i++)if(c[i]>max)max=c[i];printf("%d\n",max);}return 0; }

 

代码二：压缩路径

#include <cstdio> #include <cstring> #define N 30000 int p[N],c[N]; int n,m;int find(int x) //迭代式 {int i=x,r=x,j;while(r!=p[r])r=p[r];while(i!=r) //路径压缩 {j=p[i]; //先记录下i的双亲p[i]=r; //修改i的双亲直接与祖先相连i=j; //接下来修改原本的双亲 }return r; }int main() {int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1; i<=n; i++){ p[i]=i; c[i]=0; }for(int i=1; i<=m; i++){int x,y,u,v;scanf("%d%d",&u,&v);x=find(u);y=find(v);if(x!=y)p[x]=y;}for(int i=1; i<=n; i++) //扫描所有元素找到他们的祖先然后祖先的孩子数计数 {int x=find(i);c[x]++;}int max=0;for(int i=1; i<=n; i++)if(c[i]>max)max=c[i];printf("%d\n",max);}return 0; }

 

代码三：再修改一下统计集合元素的方法

#include <cstdio> #include <cstring> #define N 30000 int p[N],c[N]; int n,m;int find(int x) //迭代式 {int i=x,r=x,j;while(r!=p[r])r=p[r];while(i!=r) //路径压缩 {j=p[i]; //先记录下i的双亲p[i]=r; //修改i的双亲直接与祖先相连i=j; //接下来修改原本的双亲 }return r; }int main() {int T;scanf("%d",&T);while(T--){scanf("%d%d",&n,&m);for(int i=1; i<=n; i++){ p[i]=i; c[i]=1; }int max=0;for(int i=1; i<=m; i++){int x,y,u,v;scanf("%d%d",&u,&v);x=find(u);y=find(v);if(x!=y){p[x]=y;c[y]+=c[x];if(c[y]>max)max=c[y];}}printf("%d\n",max);}return 0; }

 

 

悲剧，时间没本质提高啊………………………………

总结

以上是生活随笔为你收集整理的uva 10608 FRIENDS的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。