#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

最新文章

  1. 五、jquery使用工具函数
  2. Swift 懒加载(lazy) 和 Objective-C 懒加载的区别
  3. Language
  4. 如何在MAC机器中实现移动设备WiFI上网(没有专门的无线路由器的情况)
  5. Android子线程更新UI的方法总结
  6. C#学习笔记(二)
  7. 使用urllib进行网页爬取
  8. POJ 3295 Tautology (构造题)
  9. 浅谈 js 正则字面量 与 new RegExp 执行效率
  10. Python 使用正则表达式
  11. 来手撸一个小小小小小&quot;3D引擎&quot;
  12. 为 NativeScript 项目添加 iOS / Android 平台 API 的智能感知
  13. 单点登录实现机制:web-sso
  14. Gradle 1.12用户指南翻译——第四十七章. Build Init 插件
  15. install_driver(Oracle) failed: Can&#39;t load `.../DBD/Oracle/Oracle.so&#39; for module DBD::Oracle
  16. lumen----------A facade root has not been set.
  17. windows----------如何禁用PC端微信的开机启动
  18. 更多的bash命令
  19. HierarchicalClustering:编写HierarchicalClustering层次聚类算法—Jason niu
  20. 减少网站跳转时间,增强网站数据安全——HSTS 详解

热门文章

  1. kernel module insmod错误
  2. java基础笔试题一
  3. 第四章 生命周期函数--36 结合Node手写JSONP服务器剖析JSONP原理
  4. 权限和ACL访问控制 -01-权限
  5. py实现ftp
  6. 火焰图(Flame Graphs)的安装和基本用法
  7. react浏览器回退按钮的时候传递参数
  8. 【leetcode】745. Prefix and Suffix Search
  9. MySQL--关于MySQL练习过程中遇到的AVG()函数处理空值的问题
  10. node监视文件或者文件夹的变化