题目名称 | 1678. 社交网络 |
---|---|
输入输出 | relation.in/out |
难度等级 | ★★ |
时间限制 | 1000 ms (1 s) |
内存限制 | 256 MiB |
测试数据 | 10 |
题目来源 |
|
开放分组 | 全部用户 |
提交状态 | |
分类标签 | |
分享题解 |
通过:2, 提交:5, 通过率:40% | ||||
|
100 | 1.180 s | 3.39 MiB | C++ |
|
100 | 1.236 s | 3.32 MiB | C++ |
|
10 | 13.140 s | 79.97 MiB | C++ |
|
0 | 1.184 s | 3.41 MiB | C++ |
|
0 | 19.982 s | 3.18 MiB | C++ |
本题关联比赛 | |||
板子大赛 |
关于 社交网络 的近10条评论(全部评论) |
---|
你知道吗?你和任何一个陌生人之间所间隔的人不会超六个,也就是说,最多通过六个人你就能够认识任何一个陌生人。
现在给定 $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$。