RNQOJ PID28 / [Stupid]愚蠢的宠物
2024-10-10 22:01:09
勉勉强强够着点并查集的边,题目吧他分类到并查集也无可厚非,这里与常规的并查集的区别在于要做一个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 ;
}
最新文章
- [LeetCode] Linked List Random Node 链表随机节点
- OS X 系统,修改hosts文件后不生效的问题
- MySql的连接查询
- 【转】mysql触发器的实战(触发器执行失败,sql会回滚吗)
- java容器简要概述
- EF性能之关联加载
- 谁会是 Zabbix 和 Nagios 的继任者?
- 关于Java的this关键字
- 08_XML的解析_SAX解析
- hdu 5652 India and China Origins 并查集+逆序
- 配置本地yum源的方法
- 原生AJAX如何异步提交数据?
- Velocity浅析及与Jsp、Freemarker对比
- Flashback Version/Transaction Query
- 6.基于ZMQ的游戏网络层基础架构
- 锐捷配置telnet
- 【BZOJ3669】【Noi2014】魔法森林(Link-Cut Tree)
- 基数排序-LSD
- tp 内置压缩文件zip
- Servlet快速入门