博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
CCCC L2-024 部落【并查集】
阅读量:6828 次
发布时间:2019-06-26

本文共 1260 字,大约阅读时间需要 4 分钟。

 

 首先在一行中输出这个社区的总人数、以及互不相交的部落的个数。随后对每一次查询,如果他们属于同一个部落,则在一行中输出“Y”,否则输出“N”。

/*求连通分量,先记录下原始的连通分量,每删除一个点,删去相应的边(这里用邻接矩阵便于删除边),然后再重新统计连通分量。如果和原来相同(占领的点本身是孤立的点)或者比原来多1,都不是关键城市,如果删除一个点后所计算的连通分量比原来多两个或者两个以上则发出警报,最后如果删掉的点数和总的点数相同,打印Game Over。*/#include 
using namespace std;const int maxn=10005;int fa[maxn];int cnt[maxn];void init(){ for (int i=1;i<=10000;i++){ fa[i]=i; }}int find(int x){ if (x==fa[x]) return x; return fa[x]=find(fa[x]);}void unite(int x,int y){ x=find(x); y=find(y); if (x==y) return; fa[y]=x;}bool same(int x,int y){ return find(x)==find(y);}int main(){ set
s; init(); int n; cin >> n; for (int i=0;i
> k; int a; cin >> a; s.insert(a); for (int j=1;j
> b; s.insert(b); unite(a,b); } } int sum1=0,sum2=0; for (int i=1;i<=s.size();i++){ if (fa[i]==i) sum2++; } cout << s.size() << " " << sum2 <
> n; for (int i=0;i
> x >>y; if (same(x,y)){ cout << "Y" << endl; } else{ cout << "N" << endl; } }}
View Code

 

转载于:https://www.cnblogs.com/Roni-i/p/8628382.html

你可能感兴趣的文章
2013互联网公司,年终奖有几何?
查看>>
互联网
查看>>
MySQL load data 权限相关
查看>>
ScriptManager.RegisterStartupScript失效的解决方案
查看>>
vsftpd 添加用户
查看>>
递归方法
查看>>
Sonar+maven+jenkins集成,Java代码走查
查看>>
js中点击返回顶部
查看>>
Gtest源码剖析:1.实现一个超级简单的测试框架xtest
查看>>
第三方模块的安装
查看>>
Terracotta中锁与性能的问题
查看>>
遇到Linux系统安装时窗口过大,按钮点不到,该怎么解决
查看>>
js 判断输入是否为正整数
查看>>
「收藏」一些有趣的图
查看>>
探索虚函数(二)
查看>>
李青云老人的长寿秘诀【转】
查看>>
Springboot Thymeleaf 发邮件 将html内容展示在邮件内容中
查看>>
BZOJ2434:[NOI2011]阿狸的打字机——题解
查看>>
第5件事 做一个有taste的产品人
查看>>
暂时记录
查看>>