勉勉强强够着点并查集的边,题目吧他分类到并查集也无可厚非,这里与常规的并查集的区别在于要做一个mark数组进行一下标记,展开来说就是对于要查询的A,B,先对A进行处理,把A所有的前驱也就是双亲节点进行标记,之后再对B进行查询,一旦发现B或者离B最近的那个前驱(双亲节点)被标记的话,那么当前节点就是所求了

#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
int mark[+];
int pre[+];
int main()
{
int n; while(cin>>n)
{
memset(mark,,sizeof(mark));
int a,b;
for(int i=;i<=n;i++)
{
pre[i]=i;
}
for(int i=;i<n-;i++)
{
cin>>a>>b;
pre[b]=a;
}
cin>>a>>b;
while(pre[a]!=a)
{
mark[a]=;
a=pre[a];
}
mark[a]=;
while()
{
if(mark[b])
{
cout<<b<<endl;
break;
}
else
{
b=pre[b];
}
}
}
return ;
}

最新文章

  1. [LeetCode] Linked List Random Node 链表随机节点
  2. OS X 系统,修改hosts文件后不生效的问题
  3. MySql的连接查询
  4. 【转】mysql触发器的实战(触发器执行失败,sql会回滚吗)
  5. java容器简要概述
  6. EF性能之关联加载
  7. 谁会是 Zabbix 和 Nagios 的继任者?
  8. 关于Java的this关键字
  9. 08_XML的解析_SAX解析
  10. hdu 5652 India and China Origins 并查集+逆序
  11. 配置本地yum源的方法
  12. 原生AJAX如何异步提交数据?
  13. Velocity浅析及与Jsp、Freemarker对比
  14. Flashback Version/Transaction Query
  15. 6.基于ZMQ的游戏网络层基础架构
  16. 锐捷配置telnet
  17. 【BZOJ3669】【Noi2014】魔法森林(Link-Cut Tree)
  18. 基数排序-LSD
  19. tp 内置压缩文件zip
  20. Servlet快速入门

热门文章

  1. undefined symbol: PyFPE_jbuf
  2. PHP+Ajax实现文件上传功能
  3. 如何用jquery获取form表单的值
  4. java使用Filter过滤器对Response返回值进行修改
  5. struts2.5入门
  6. Web开发敏捷之道应用Rails 进行Web开发(原书第4版)遇到的问题
  7. JS解决在提交form表单时某个值不存在 alter弹窗点确定不刷新界面
  8. sublime安装PackageControl提示失败(被墙了)
  9. 我在Python学习中遇到的问题一
  10. I2C与SMBus