题目描述

蓝桥幼儿园的学生是如此的天真无邪，以至于对他们来说，朋友的朋友就是自己的朋友。

小明是蓝桥幼儿园的老师，这天他决定为学生们举办一个交友活动，活动规则如下：

小明会用红绳连接两名学生，被连中的两个学生将成为朋友。

小明想让所有学生都互相成为朋友，但是蓝桥幼儿园的学生实在太多了，他无法用肉眼判断某两个学生是否为朋友。于是他起来了作为编程大师的你，请你帮忙写程序判断某两个学生是否为朋友（默认自己和自己也是朋友）。

输入描述

第 1 行包含两个正整数 N,M，其中 N表示蓝桥幼儿园的学生数量，学生的编号分别为  1∼N。

之后的第 2∼M+1 行每行输入三个整数，op , x , y

• 如果 op = 1，表示小明用红绳连接了学生 x和学生 y 。
• 如果 op=2，请你回答小明学生 x 和 学生 y 是否为朋友。

1≤N,M≤2*10^5 ,1≤x,y≤N。

输出描述

对于每个 op=2 的输入，如果 x和 y 是朋友，则输出一行 YES，否则输出一行 NO。

输入输出样例

示例 1

输入

1. 5 5
2. 2 1 2
3. 1 1 3
4. 2 1 3
5. 1 2 3
6. 2 1 2

输出

1. NO
2. YES
3. YES

运行限制

• 最大运行时间：3s
• 最大运行内存: 256M

思路：

采用并查集的方法。

1。设计初始化函数init()，初始化数组s，将编号为1~N的N个对象划分为不相交的集合，在每个集合中选择一个元素代表整个集合。

2.设计查找函数find(),通过递归的方法返回x的所在集合的代表元素。

3.设置合并函数merge()，寻找x,y的根节点，如果根节点不一致，则改成一致

主函数：

当op==1时，读入x,y合并集合s[x],s[y]，使得s[x]=s[y]

当op==2时，寻找x和y的根节点，通过比较根节点是否一致判断x和y是否在一个集合中。如果在，说明x,y是朋友，输出YES，否则输出NO。

代码

1. N=800000
2. s=[]
3. 
4. def init():
5. for i in range(N):
6.         s.append(i)
7. 
8. def find(a):
9. if a!=s[a]:
10.         s[a]=find(s[a])
11. return s[a]
12. 
13. def merge(x,y):
14.     x=find(x)
15.     y=find(y)
16. if x!=y:
17.         s[x]=s[y]
18. 
19. n,m=map(int,input().split())
20. init()
21. for i in range(m):
22.     op,x,y=map(int,input().split())
23. if op==1 :
24. merge(x,y)
25. if op==2 :
26. if find(x)==find(y):
27.             print("YES")
28. else:
29.             print("NO")