题目名称 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$。