E - More is better (并查集)
2024-08-27 08:30:01
Mr Wang wants some boys to help him with a project. Because the project is rather complex, the more boys come, the better it will be. Of course there are certain requirements.
Mr Wang selected a room big enough to hold the boys. The boy who are not been chosen has to leave the room immediately. There are 10000000 boys in the room numbered from 1 to 10000000 at the very beginning. After Mr Wang's selection any two of them who are
still in this room should be friends (direct or indirect), or there is only one boy left. Given all the direct friend-pairs, you should decide the best way.
Mr Wang selected a room big enough to hold the boys. The boy who are not been chosen has to leave the room immediately. There are 10000000 boys in the room numbered from 1 to 10000000 at the very beginning. After Mr Wang's selection any two of them who are
still in this room should be friends (direct or indirect), or there is only one boy left. Given all the direct friend-pairs, you should decide the best way.
1 ≤ A, B ≤ 10000000)
4
1 2
3 4
5 6
1 6
4
1 2
3 4
5 6
7 8
4
2
暴力枚举,中间有一小部分的优化
把连在一起的通过join连接在一起然后通过枚举有都少个孩子节点有相同的父亲
Select Code
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int par[10000005];
void init(int n)
{
for(int i=1; i<=10000005; i++)
par[i]=i;
}
int find(int x)
{
if(par[x]==x)
return x;
else
return par[x]=find(par[x]);
}
void join(int x, int y)
{
int fx=find(x),fy=find(y);
if(fx!=fy)
{
par[fx]=fy;
}
}
int main()
{
int n;
while(~scanf("%d",&n))
{
if(n==0) //特判????
{
printf("1\n");
continue;
}
init(n);
int maxn=0;
for(int i=1; i<=n; i++)
{
int a,b;
scanf("%d%d",&a,&b);
join(a,b);
if(max(a,b)>maxn) //优化
{
maxn=max(a,b) ;
}
}
int sum=0,ans=0;
for(int j=1; j<=maxn; j++)
{
int ans=0;
if(par[j]==j)
for(int i=1; i<=maxn; i++)
{
if(find(i)==j) //find(i)与par[i]不同??
ans++;
}
sum=max(sum,ans);
}
printf("%d\n",sum);
}
return 0;
}
最新文章
- Exception Type &; Exception Code
- Firemonkey TEdit 切换不同 KeyboardType 样式
- Python开发【第十三篇】:jQuery(二)
- .Net MVC 入门之Razor语法
- Spring Security(02)——关于登录
- asp.net-mvc验证码 asp.net-mvc c#验证码
- nodejs的简单爬虫
- IIS Express总结
- 微信小程序版本自动更新弹窗提示
- BZOJ1069 SCOI2007 最大土地面积 凸包、旋转卡壳
- Ex 2_5 求解递推式..._第三次作业
- [Docker] Running Multiple Containers for an Angular, Node project
- struct 和typedef struct
- python页面解析_beautifulsoup试玩
- Java反射,参数为数组
- UML图中聚合、组合、关联、依赖、泛化的强弱关系
- 论文笔记——Factorized Convolutional Neural Networks
- jQuery中的100个技巧(译)
- [翻译] NSRegexTester
- RabbitMQ基础篇
热门文章
- Creating Self-Signed SSL Certificates
- LUA表 pairs, ipairs输出顺序问题
- springmvc web.xml配置之 -- DispatcherServlet
- eclipse-jee-mars-2-win32-x86_64安装activiti
- 解题报告-603. Consecutive Available Seats
- [mongoDB] mongoDb
- Laravel 配置文件操作方法
- linux 关键发行版及其关系图
- 修改数据库中的内容报错:PropertyAccessException:Null value was assinged to a property of primitive type setter of
- [operator]ubuntu + git