天梯赛 L2-024. 部落
2024-10-06 05:42:59
题解:并查集,这里要用路径压缩来优化
代码:// 这里范围理错了, 浪费20分钟debug
#include <set>
#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int maxn=;
int fa[maxn];
int n; int Find(int x)
{
//
int temp=x;
while(fa[temp]!=temp)
{
temp=fa[temp];//
} while(fa[x]!=temp) // 路劲压缩
{
int zz=fa[x];
fa[x]=temp;
x=zz;
} return temp; // root
} void Merge(int x,int y)
{
int fx=Find(x);// root of x
int fy=Find(y);// root of y
if(fx != fy)
{
fa[fx] = fy;
}
} int main()
{
cin>>n;
int pre,now;
set<int >st;
for(int i=;i<maxn;i++) fa[i]=i;
for(int i=;i<=n;i++)
{
int k;
cin>>k;
for(int j=;j<=k;j++)
{
if(j==)
{
scanf("%d",&now);
}
else
{
pre=now;
// cout<<"pre:"<<pre<<endl; scanf("%d",&now);
Merge(pre,now);//
// cout<<fa[2]<<endl;
// cout<<pre<<' '<<now<<' '<<fa[pre]<<' '<<fa[now]<<endl;
}
st.insert(now);
}
}
int q;
cin>>q;
int num=;
for(int i=;i<=st.size();i++)
{
if(fa[i]==i)
{
num++;
// cout<<i<<endl;
}
}
cout<<st.size()<<" "<<num<<endl;
while(q--)
{
int a,b;
scanf("%d %d",&a,&b);
int fa=Find(a);
int fb=Find(b);
if(fa==fb) cout<<"Y"<<endl;
else cout<<"N"<<endl;
}
// for(int i=1;i<=st.size();i++) cout<<fa[i]<<" ";
// cout<<fa[2]<<endl;
return ;
}
最新文章
- Shell入门教程:流程控制(7)break和continue
- PS Web切图界面设置
- java程序操作Geometry对象
- |原创|unity 4.3 2D功能SpriteRenderer修改颜色的方法
- mysql convert
- [km] 如何判断一个直播系统是否使用的是RTMP
- OO之美3
- 关于 Delphi 中的Sender和易混淆的概念(转)
- 谷歌YSlow准则
- spring框架应用系列一:annotation-config自动装配
- laravel view not found
- window.location.replace和window.location.href区别
- 【题解】JSOIWC2019 Round3
- ckeditor_学习(1) 基本使用
- python3 练习题(多级菜单)
- delphi正则表达式学习笔记(二)
- [Spring]IOC控制反转和DI依赖注入
- git 撤销add和commit
- word转html 压缩图片网站
- CF 258 D. Little Elephant and Broken Sorting
热门文章
- Visual Studio 2019更新到16.2.1
- C++main函数命令行选项——学习笔记
- Vue动态路由 Get传值
- CDH 部署 Hadoop:5.开始安装
- centos7设置rsyslog日志服务集中服务器
- opencv4 mask_rcnn模型调(c++)
- 123457123456#1#----com.MC.EnglishGame98--前拼后广--jp英语-mc
- spring 使用@AspectJ注解开发Spring AOP
- Java extract amplitude array from recorded wave
- WebSocket接收音频,并推送到声卡上