题解:并查集,这里要用路径压缩来优化

代码:// 这里范围理错了, 浪费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 ;
}

最新文章

  1. Shell入门教程:流程控制(7)break和continue
  2. PS Web切图界面设置
  3. java程序操作Geometry对象
  4. |原创|unity 4.3 2D功能SpriteRenderer修改颜色的方法
  5. mysql convert
  6. [km] 如何判断一个直播系统是否使用的是RTMP
  7. OO之美3
  8. 关于 Delphi 中的Sender和易混淆的概念(转)
  9. 谷歌YSlow准则
  10. spring框架应用系列一:annotation-config自动装配
  11. laravel view not found
  12. window.location.replace和window.location.href区别
  13. 【题解】JSOIWC2019 Round3
  14. ckeditor_学习(1) 基本使用
  15. python3 练习题(多级菜单)
  16. delphi正则表达式学习笔记(二)
  17. [Spring]IOC控制反转和DI依赖注入
  18. git 撤销add和commit
  19. word转html 压缩图片网站
  20. CF 258 D. Little Elephant and Broken Sorting

热门文章

  1. Visual Studio 2019更新到16.2.1
  2. C++main函数命令行选项——学习笔记
  3. Vue动态路由 Get传值
  4. CDH 部署 Hadoop:5.开始安装
  5. centos7设置rsyslog日志服务集中服务器
  6. opencv4 mask_rcnn模型调(c++)
  7. 123457123456#1#----com.MC.EnglishGame98--前拼后广--jp英语-mc
  8. spring 使用@AspectJ注解开发Spring AOP
  9. Java extract amplitude array from recorded wave
  10. WebSocket接收音频,并推送到声卡上