博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
More is better
阅读量:6615 次
发布时间:2019-06-24

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

真的无语了,一个并查集的水题,竟然做了两个多小时,我都怀疑我自己了,还有智商么?

题意,找出最多认识人的集合

我手残了N次 ,本题1000ms,数组10000000,所以要用哈希查找

#include 
#include
#include
#include
using namespace std;int n;int bin[10000001];int ta[10000001];int findx(int x){ int r=x; while(bin[r]!=r) { r=bin[r]; } int k,j; k=x; while(k!=r) { j=bin[k]; bin[k]=r; k=j; } return r;}void merge(int x,int y){ int fx=findx(x); int fy=findx(y); if(fx!=fy) bin[fy]=fx;}int main(){ int x,y,max1; while(scanf("%d",&n)!=EOF) { memset(ta,0,sizeof(ta)); for(int i=1;i<=1000000;i++) bin[i]=i; //while(n--)//已经多次手惨了,这次贴出来惊醒一下 for(int i=1;i<=n;i++) { scanf("%d%d",&x,&y); merge(x,y); } for(int i=1;i<10000001;i++) { ta[findx(i)]++;//算法的核心;哈希 } max1=ta[1]; //刚才把n弄成了0 for(int i=2;i<10000001;i++) { if(ta[i]>max1) max1=ta[i]; } printf("%d\n",max1); } return 0;}
View Code

 

转载地址:http://kmhso.baihongyu.com/

你可能感兴趣的文章
php使用curl下载指定大小的文件
查看>>
VS2013创建Node.js C++ Addons的过程
查看>>
amaze ui中的icon button
查看>>
tcp 三次握手
查看>>
XML中添加换行符
查看>>
在C#中使用属性控件添加属性窗口
查看>>
printf()详解之终极无惑
查看>>
交叉检验---训练数据,验证数据和测试数据
查看>>
AspNetPager分页控件配置
查看>>
备胎的养成记KeepAlived实现热备负载
查看>>
相等与全等
查看>>
VS无法设置断点的解决方案
查看>>
Android -- 再来一发Notification
查看>>
从尾到头打印链表
查看>>
【hibernate】 hibernate的主键策略
查看>>
单表代替密码原理及算法实现
查看>>
如何让VS检查函数和类Comment的添加情况
查看>>
Linq案例
查看>>
制作播放视频关灯效果
查看>>
【POI】解析xls报错:java.util.zip.ZipException: error in opening zip file
查看>>