同和创作矩阵 › ›博文归档› 技术博文归档 › 查看内容

1314_并查集

2022-5-16 18:17| 发布者: Hocassian| 查看: 41| 评论: 0|原作者: 肇庆学院ACM合集

摘要:

C:\Users\Administrator\Downloads\2019-10-12-10-14-2-89503764336700-Problem List-采集的数据-后羿采集器.html

Pro.ID

1314

Title

并查集

Title链接

http://10.20.2.8/oj/exercise/problem?problem_id=1314

AC

336

Submit

1114

Ratio

30.16%

时间&空间限制

Time Limit: 16000/8000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

描述

并查集的一个常用场合是：快速判断两个元素是否在同一个集合。

并查集的原理与实现请参考Article里面的文章。

输入

测试用例的第一行是一个整数 n ( 0 < n < 100000 ) ，表示一共有多少个元素。每个元素定义为非负整数，范围是 0 ～ n-1

接下来是一个正整数m ( 0 < m < n*(n-1) )，表示有m个关系。

接下来有m行，每行是两个非负整数a和b，表示a和b之间有关系（即在同一个集合）。

接下来是一个正整数t，表示有t个问题。

接下来有t行，每行是两个非负整数x和y，表示提问x和y是否在同一个集合。

输出

Description

并查集的一个常用场合是：快速判断两个元素是否在同一个集合。

并查集的原理与实现请参考Article里面的文章。

Input

测试用例的第一行是一个整数 n ( 0 < n < 100000 ) ，表示一共有多少个元素。每个元素定义为非负整数，范围是 0 ～ n-1

接下来是一个正整数m ( 0 < m < n*(n-1) )，表示有m个关系。

接下来有m行，每行是两个非负整数a和b，表示a和b之间有关系（即在同一个集合）。

接下来是一个正整数t，表示有t个问题。

接下来有t行，每行是两个非负整数x和y，表示提问x和y是否在同一个集合。

Output

对应输入的t个问题的次序输出t行结果，如果x和y是在同一个集合中，则输出y，否则n 。

Sample Input

5
3
0 3
2 1
4 2
3
0 4
1 4
1 3

Sample Output

n
y
n

Hint

在 "每行两个非负整数a和b，表示a和b之间有关系（即在同一个集合）"中，可能存在重复的关系，如：

1 5
5 1

Author

John

样例输入