HDU_1856_带权并查集
2024-08-25 21:58:47
有10000000个同学,他们之间可能是直接朋友或者间接朋友,问最大的朋友圈有多少人。
一直觉得10000000的数组开不了,用map优化了一下,结果能开,且10000000也不会超时。。。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<algorithm>
#include<map>
using namespace std;
#define N 200005 int father[N];
int number[N]; int findFa(int num)
{
if(father[num]!=num)
father[num]=findFa(father[num]);
return father[num];
} void Merge(int a,int b)
{
int fa=findFa(a);
int fb=findFa(b);
if(fa!=fb)
{
father[fa]=fb;
number[fb]+=number[fa];
}
} map<int,int> ma;
int size;
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
size=;
ma.clear();
for(int i=; i<=N; i++)
{
father[i]=i;
number[i]=;
}
for(int i=; i<n; i++)
{
int a,b;
scanf("%d%d",&a,&b);
if(ma[a]==)
ma[a]=size++;
if(ma[b]==)
ma[b]=size++;
Merge(ma[a],ma[b]);
}
int res=;
for(int i=; i<=N; i++)
{
//if(i<10)
// cout<<number[i]<<" ";
if(father[i]==i)
res=max(res,number[i]);
}
printf("%d\n",res);
}
return ;
}
最新文章
- curl的登录总结
- Erlang--proplists结构解析
- 【译】用jQuery 处理XML-- DOM(文本对象模型)简介
- [C#] 谈谈异步编程async await
- 解决php与IIs的冲突
- struts2拦截器配置;拦截器栈;配置默认拦截器;拦截方法的拦截器MethodFilterInterceptor;完成登录验证
- uva1638Pole Arrangement
- 【原创】Linux opensource-src-4.3.2.tar.gz的安装。
- NodeJs简单七行爬虫--爬取自己Qzone的说说并存入数据库
- SERVERPROPERTY方法说明
- iOS 的 APP 如何适应 iPhone 5s/6/6Plus 三种屏幕的尺寸?(转)
- python 10 min系列三之小爬虫(一)
- Android开发技巧——实现在图标文本底部导航栏(更新)
- RMQ问题再临
- [国嵌攻略][165][usb下载线驱动设计]
- C# decimal 去掉小数点后的无效0
- C# GetValue 正则获取开始结束代码
- Linux系统网络编程中TCP通讯socket--send导致进程被关闭
- Lambda表达式概念与基本语法
- java中转译符用";\\";的几种特殊字符
热门文章
- eclipse自动创建项目出错Cannot change version of project facet Dynamic Web Module to 2.3.
- sphinx源码分析总结
- 为ios app添加广告条
- (unix domain socket)使用udp发送>;=128K的消息会报ENOBUFS的错误
- hdu 2476 (string painter) ( 字符串刷子 区间DP)
- HardFault_Handler 输出日志信息
- bzoj 2561: 最小生成树【最小割】
- JAVA中抽象类不可以实例化,却可以创建数组
- [BZOJ3531] Peaks加强版
- (二)python高级特性