有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 ;
}

最新文章

  1. curl的登录总结
  2. Erlang--proplists结构解析
  3. 【译】用jQuery 处理XML-- DOM(文本对象模型)简介
  4. [C#] 谈谈异步编程async await
  5. 解决php与IIs的冲突
  6. struts2拦截器配置;拦截器栈;配置默认拦截器;拦截方法的拦截器MethodFilterInterceptor;完成登录验证
  7. uva1638Pole Arrangement
  8. 【原创】Linux opensource-src-4.3.2.tar.gz的安装。
  9. NodeJs简单七行爬虫--爬取自己Qzone的说说并存入数据库
  10. SERVERPROPERTY方法说明
  11. iOS 的 APP 如何适应 iPhone 5s/6/6Plus 三种屏幕的尺寸?(转)
  12. python 10 min系列三之小爬虫(一)
  13. Android开发技巧——实现在图标文本底部导航栏(更新)
  14. RMQ问题再临
  15. [国嵌攻略][165][usb下载线驱动设计]
  16. C# decimal 去掉小数点后的无效0
  17. C# GetValue 正则获取开始结束代码
  18. Linux系统网络编程中TCP通讯socket--send导致进程被关闭
  19. Lambda表达式概念与基本语法
  20. java中转译符用&quot;\\&quot;的几种特殊字符

热门文章

  1. eclipse自动创建项目出错Cannot change version of project facet Dynamic Web Module to 2.3.
  2. sphinx源码分析总结
  3. 为ios app添加广告条
  4. (unix domain socket)使用udp发送&gt;=128K的消息会报ENOBUFS的错误
  5. hdu 2476 (string painter) ( 字符串刷子 区间DP)
  6. HardFault_Handler 输出日志信息
  7. bzoj 2561: 最小生成树【最小割】
  8. JAVA中抽象类不可以实例化,却可以创建数组
  9. [BZOJ3531] Peaks加强版
  10. (二)python高级特性