博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
uva 10608 Friends 并查集
阅读量:4575 次
发布时间:2019-06-08

本文共 1048 字,大约阅读时间需要 3 分钟。

/*题目:    n个人中有m对人互为朋友,若a认识b,b认识c,则a认识c,问这n个人中最多有多少人    相互认识分析:    并查集实现,把互为朋友的放置在同一集合中,询问最大人数时可以使用计数器计算该    人所在集合的父节点的数字*/#include 
#include
#include
using namespace std;const int X = 30002;int p[X],cnt[X],n,m;int find_set(int x){ if(x!=p[x]) p[x] = find_set(p[x]); return p[x];}int main(){ freopen("sum.in","r",stdin); freopen("sum.out","w",stdout); int t,x,y; cin>>t; while(t--) { memset(cnt,0,sizeof(cnt)); scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) p[i] = i; for(int i=1;i<=m;i++) { scanf("%d%d",&x,&y); x = find_set(x); y = find_set(y); if(x!=y) p[y] = x; } for(int i=1;i<=n;i++) { x = find_set(i); cnt[x]++; } int ans = 0; for(int i=1;i<=n;i++) ans = max(cnt[i],ans); cout<
<

 

转载于:https://www.cnblogs.com/yejinru/archive/2012/06/14/2549900.html

你可能感兴趣的文章
Django REST Framework自定义token认证
查看>>
Django REST Framework自定义权限
查看>>
django集成swagger2.0以上版本
查看>>
Linux下部署多个tomcat
查看>>
linux下tomcat加入到系统服务systemctl
查看>>
区块链七大应用场景
查看>>
消息队列常见的5种使用场景
查看>>
9种 分布式ID生成方式
查看>>
JAVA开发技术工具汇总(一)
查看>>
机器学习和深度学习综述
查看>>
使用Python和Numpy构建神经网络模型
查看>>
使用Matplotlib简单作图案例
查看>>
Linux下Redis部署
查看>>
tomcat8域名非法解析解决方法
查看>>
Oracle数据库clob字段insert报错
查看>>
监控Linux系统信息【Grafana+Prometheus+node_exporter】
查看>>
使用docker安装Jenkins
查看>>
NextCloud搭建私有云盘【可多设备同步】
查看>>
windowns下安装虚拟化环境 virtualenv
查看>>
Django路由分发【>=2.2.X】
查看>>