并查集练习(0743) SWUST OJ
2024-08-24 23:31:43
#include<iostream>
#include<cstring>
using namespace std;
int a[];
int n,m,l,ci,di; int root(int x) //找到根节点
{
int r = x;
while(r != a[r])
r = a[r];
int i = x,j;
while(i != r) //压缩路径
{
j = a[i];
a[i] = r;
i = j;
}
return r;
} void mix(int x,int y) //混合
{
int fx = root(x),fy = root(y);
if(fx != fy)
a[fy] = fx; //根节点的值覆盖
} int main()
{
int i,j,t1,t2;
// memset(a,0,sizeof(a)); //过程中超时了,除去这一条就AC了
cin>>n>>m;
for(i = ;i <= n;i++)
a[i] = i;
for(i = ;i <= m;i++)
{
cin>>ci>>di;
mix(ci,di);
}
cin>>l;
for(i = ;i <= l;i++)
{
cin>>t1>>t2;
if(root(t1) != root(t2))
cout<<"They aren't relative!"<<endl;
else
cout<<"They are relative!"<<endl;
} return ;
}
这是自学的并查集,然后在oj上敲的题。有关并查集的学习可以百度。
-----15:44:28 2017-06-10
最新文章
- 五、jquery使用工具函数
- Swift 懒加载(lazy) 和 Objective-C 懒加载的区别
- Language
- 如何在MAC机器中实现移动设备WiFI上网(没有专门的无线路由器的情况)
- Android子线程更新UI的方法总结
- C#学习笔记(二)
- 使用urllib进行网页爬取
- POJ 3295 Tautology (构造题)
- 浅谈 js 正则字面量 与 new RegExp 执行效率
- Python 使用正则表达式
- 来手撸一个小小小小小";3D引擎";
- 为 NativeScript 项目添加 iOS / Android 平台 API 的智能感知
- 单点登录实现机制:web-sso
- Gradle 1.12用户指南翻译——第四十七章. Build Init 插件
- install_driver(Oracle) failed: Can&#39;t load `.../DBD/Oracle/Oracle.so&#39; for module DBD::Oracle
- lumen----------A facade root has not been set.
- windows----------如何禁用PC端微信的开机启动
- 更多的bash命令
- HierarchicalClustering:编写HierarchicalClustering层次聚类算法—Jason niu
- 减少网站跳转时间,增强网站数据安全——HSTS 详解