个人中心
文章发布
退出
作者热门文章
- ubuntu12.04环境下使用kvm ioctl接口实现最简单的虚拟机
- Ubuntu 通过无线网络安装Ubuntu Server启动系统后连接无线网络的方法
- 在Ubuntu上搭建网桥的方法
- ubuntu 虚拟机上网方式及相关配置详解
24
4
CFSDN坚持开源创造价值，我们致力于搭建一个资源共享平台，让每一个IT人在这里找到属于你的精彩世界.
这篇CFSDN的博客文章C++并查集亲戚(Relations)算法实例由作者收集整理，如果你对这篇文章有兴趣，记得点赞哟.
本文实例讲述了C++并查集亲戚(Relations)算法。分享给大家供大家参考。具体分析如下:
题目： 亲戚(Relations) 。
或许你并不知道，你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥的表姐的孙子。如果能得到完整的家谱，判断两个人是否亲戚应该是可行的，但如果两个人的最近公共祖先与他们相隔好几代，使得家谱十分庞大，那么检验亲戚关系实非人力所能及.在这种情况下，最好的帮手就是计算机.
为了将问题简化，你将得到一些亲戚关系的信息，如同Marry和Tom是亲戚，Tom和B en是亲戚，等等。从这些信息中，你可以推出Marry和Ben是亲戚。请写一个程序，对于我们的关心的亲戚关系的提问，以最快的速度给出答案.
参考输入输出格式 输入由两部分组成.
第一部分以N，M开始。N为问题涉及的人的个数(1 ≤ N ≤ 20000)。这些人的编号为1,2,3,…,N。下面有M行(1 ≤ M ≤ 1000000)，每行有两个数ai, bi，表示已知ai和bi是亲戚. 。
第二部分以Q开始。以下Q行有Q个询问(1 ≤ Q ≤ 1 000 000)，每行为ci, di，表示询问ci和di是否为亲戚.
对于每个询问ci, di，若ci和di为亲戚，则输出Yes，否则输出No.
样例输入与输出 。
输入 10 7 2 4 5 7 1 3 8 9 1 2 5 6 2 3 3 3 4 7 10 8 9 。
输出 Yes No Yes 。
如果这道题目不用并查集，而只用链表或数组来存储集合，那么效率很低，肯定超时.
代码如下:
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
|
#include <iostream>
#include <cstdio>
using
namespace
std;
int
father[20010];
//father[i]表示i的父亲
int
Find(
int
a)
//查找其父亲并压缩路径
{
if
(father[a] != a)
father[a] = Find(father[a]);
return
father[a];
}
int
main()
{
int
N,M;
int
a,b;
scanf
(
"%d%d"
,&N,&M);
//给每个元素建立一个集合
for
(
int
i = 1 ; i <= N ; ++i)
father[i] = i;
//合并
for
(
int
i = 0 ; i < M ; ++i)
{
scanf
(
"%d%d"
,&a,&b);
a = Find(a);
b = Find(b);
father[a] = b;
}
//查询
scanf
(
"%d"
,&M);
while
(M--)
{
scanf
(
"%d%d"
,&a,&b);
a = Find(a);
b = Find(b);
if
(a == b)
printf
(
"YES\n"
);
else
printf
(
"NO\n"
);
}
return
0;
}
|
希望本文所述对大家的C++程序设计有所帮助.
最后此篇关于C++并查集亲戚(Relations)算法实例的文章就讲到这里了,如果你想了解更多关于C++并查集亲戚(Relations)算法实例的内容请搜索CFSDN的文章或继续浏览相关文章，希望大家以后支持我的博客！ 。
24
4
0
我知道，关系数据库是一种数据库，其中一个表中的字段链接到其他表中的行，就像这样。 但我不明白这对我作为网络开发人员意味着什么! 据我所知，具有联接和嵌套选择的查询会降低性能(尤其是具有数十个联接的 d
我正在逻辑层面上设计一个数据库，以便稍后将其传递给程序员来交付。我只是粗略地了解它们的工作原理，所以我很难简洁地表达我的问题。这是我的问题: 我有一个名为 MEANINGS 的表。 我有一个名为 WO
在 Jira 中，将项目链接在一起既简单又实用。 例如，您可以轻松克隆一个问题:创建问题 100，将其克隆到 101。100 然后显示“这个问题有一个克隆:101”，然后 101 显示“这个问题是一个
所以我有这些实体: Group { id: number; name: string; persons: Person[]; } Person { name: stri
我真不敢相信，经过 5 年的 Rails 编程，我还没有想出一个好的解决方案来解决这个常见问题。另外，我假设这个特定问题有 100 个答案，但我不知道定义(关系？协会？等)来很好地搜索它。所以我们开始
我想在我的数据库记录中包含动态字段。 例如:我想构建一个应用程序供用户创建自己的表单。 用户可以创建以下表单: 个人资料: 全名 街道 工作 电话 首页 工作 移动 兴趣 兴趣 1 兴趣 2 兴趣 3
共有三个表:businesses、categories、categorizations、 CREATE TABLE businesses ( id SERIAL PRIMARY KEY, na
这个问题在这里已经有了答案: How can I vertically center a div element for all browsers using CSS? (48 个答案) 关闭 6
对于问题的错误措辞，我们深表歉意。我是 stackoverflow 的新手，也是 PIG 的新手，正在尝试自己进行实验。 我有一个处理 words.t 文件和 data.txt 文件的场景。 文字.t
关于像Cassandra 这样的反革命NoSQL 数据库的讨论很多。 , CouchDB , Hypertable , MongoDB , Project Voldemort , BigTable ，
我的处境与ICTylor's post here 类似。 . 所以我有: user1=User.find(1); user2=User.find(2); written=Micropost.where
尝试获取与事件关联的用户列表。这是我 Eloquent 模型: 用户.php: public function fbevents() { $this->belongsToMany('Fbeve
我有一个在 MySQL 数据库上运行的 Web 应用程序(正在开发中)。我正在考虑将我的应用程序迁移到 Google App Engine，并希望更好地了解如何将我的简单关系数据库模型转换为非关系方法
我应该在构造函数中放入什么:与实例相关的东西还是与类相关的东西？ 考虑这段代码: var count = 0 TView = function (x, y) { this.x = x, this.y
我正在努力使用 postgreSQL，因为我不知道如何将 A 类型的一个实例链接到 B 类型的一组实例。我将举一个简短的例子: 假设我们要建立一个包含音乐专辑和人物的数据库，每个人都有一个他们最喜欢的
我需要检索一个对象并获取关系和嵌套关系。 所以，我有以下三个模型: 用户模型: module.exports = { attributes: { name: { type: '
给定一个表定义: Articles: art_id | name -------|-------------- 1 | article1 2 | article2 3
谁能举例说明“em 是相对于字体大小的，% 是相对于父元素的”？ 相对于字体大小和相对于父元素是什么意思？ 最佳答案 考虑一下您是否要在另一个框内定义一个框的高度。如果您将高度指定为 50%，它将是包
我有一个多对多关系，当我加载位于此关系一侧的实体时，我希望将另一侧相关实体的 ArrayCollection 视为其属性。然而，这并没有发生——加载的 ArrayCollection 中没有任何元素，
Relation#update(id, attributes) 文档提到“无论对象是否成功保存到数据库，都会返回结果对象。”，而 Relation#update_all (updates, condi
我是一名优秀的程序员,十分优秀！