题目名称 1678. 亲戚关系
输入输出 relation.in/out
难度等级 ★★
时间限制 1000 ms (1 s)
内存限制 256 MiB
测试数据 10
题目来源 Gravatarsyzhaoss 于2025-01-20加入
开放分组 全部用户
提交状态
分类标签
并查集
分享题解
通过:2, 提交:5, 通过率:40%
Gravatar天寸梦幻 100 1.180 s 3.39 MiB C++
GravatarChenBp 100 1.236 s 3.32 MiB C++
Gravatar天寸梦幻 10 13.140 s 79.97 MiB C++
Gravatar01 0 1.184 s 3.41 MiB C++
Gravatar天寸梦幻 0 19.982 s 3.18 MiB C++
本题关联比赛
板子大赛
关于 亲戚关系 的近10条评论(全部评论)

1678. 亲戚关系

★★   输入文件:relation.in   输出文件:relation.out   简单对比
时间限制:1 s   内存限制:256 MiB

【题目背景】

大家应该练习过亲戚这道题目,所以背景就不需要详细介绍了。

按照常理,亲戚关系并不是一成不变的,一般会通过联姻、结拜等出现新的亲戚关系可能使得原来两个八竿子打不着的人成为亲戚。

【题目描述】

现在给定$n$个人,假设这$n$个人开始时都和其他人没有亲戚关系,现在逐步给他们之间添加亲戚关系,当然中间也会询问是两个人是否有亲戚关系。

【输入格式】

第一行两个整数$n,m$,表示总共有$n$个人,有$m$次操作。

接下来$m$行,每行三个整数$op, x, y$。

若$op=0$,则说明$x$和$y$之间新增了亲戚关系。

若$op=1$,则在当前已知的亲戚关系情况下,询问$x$和$y$是否为亲戚。

【输出格式】

对于每个询问,若$x$和$y$为亲戚,则输出Yes,否则输出No

【样例输入】

9 10
0 2 4
0 5 7
0 1 3
0 1 2
1 3 4
0 8 9
0 5 6
1 8 5
0 2 3
1 7 6

【样例输出】

Yes
No
Yes

【数据范围与约定】

对于$30%$的数据,有$n\leq 100,m\leq 2000$。

对于$100%$的数据,有$n\leq 2\times 10^4,m\leq 10^5$。