同时正在备战蓝桥杯 题解如有不足请多批评指正
大一双非本科在读
目标是进大厂
问题分析：这是一道考察并查集的经典例题。
何为并查集？并查集是一种（树型）数据结构 ，用于处理一些不相交集合的合并及查询问题。
思想：用一个数组表示了整片森林，树的根节点唯一标识了一个集合，我们只要找到了某个元素的的树根，就能确定它在哪个集合里。例如给出数组parent=[0,1,5,1,3,1]，parent[i]代表结点i的父结点（很形象吧！？）
观察数组，我们知道:parent[2]=5 ，说明了结点2的父节点是5
再来：parent[5]=1，说明了结点5的父节点是1
再来:parent[1]=1,说明了结点1的父节点是1
对上面这行可能有疑惑：我们先记住，若parent[i]=i 则i是一个集合内的根节点
那么他有什么作用：如果一个结点j 它的父节点的父节点的父节点的父节点.....是i
说明了j和它的父节点和它的父节点的父节点和....一共这么多结点，对于每一个结点，都可以访问到i结点。我们不如把它叫做祖先（能够访问 类似于 含有血缘关系，你和你的祖先，你的父亲的祖先，你的父亲的父亲的祖先都有血缘关系。）
因此这么多结点就构成了一个集合（代表集合的对象是根节点（祖先））
所以对于刚刚提到的数组，由于结点5可以访问到祖先>>1，所以5和1有血缘关系，即5属于祖先1代表的集合，由于结点2的父节点是5，所以它可以通过父节点5访问到祖先>>1，所以2和1有血缘关系，即2属于祖先1代表的集合。
因此我们要判断两个结点是否属于同一个集合，可以借助访问各自的祖先加以判断。
如果祖先相同，那么属于同一集合，否则不属于同一集合。
对于上述数组结点0和结点1就不属于同一集合
所以下面给出访问祖先的代码:（关于优化下面会阐述）
def find_root(x): while x!=parent[x]:3如果不是祖先 就访问自己的父节点 x=parent[x] return x
那么上面这段代码就是代表了并查集的思想之一：查询
那么下面我们研究并查集的另一个思想：合并
再次给出上面那个例子parent=[0,1,5,1,3,1]
我们知道结点1，2，3，4，5同属于一个集合（用结点1来标识）
由于parent[0]=0 说明0是一个集合的祖先，这个集合用结点0来标识
由于以结点0为代表的集合元素个数为1，比较特殊，我们不妨给他（集合）添加两个结点
分别是结点6，结点7，因此parent=[0,1,5,1,3,1,0,0]
所以现在 结点0，6，7同属于一个集合（用结点0来标识）
下面研究合并，何为合并？就是将两个集合变为为一个集合
容易想到，我们可以把结点0（祖先）作为结点1的子结点，换句话说，把结点1作为结点0的父节点。
那么这样子有什么用：我们知道用结点0来标识的集合中的结点，都可以访问到结点0，现在结点0又可以访问到结点1，所以用结点0来标识的集合中的结点，都可以访问到结点1，因此用结点1来标识的集合 结点数目扩大了！ 这不正达到了我们想要的效果吗？
简言之 集合A和集合B原本分属两大家族，把A的祖先作为B祖先的孩子，因而集合A和B中的所有结点都有了血缘关系，实现了家族合并。
所以下面给出合并的代码：
def union(x,y):#合并
x_root,y_root=find(x),find(y)
parent[x_root]=y_root#一般的x_root!=y_root，直接合并过去
#如果x_root=y_root,合并本身，没有发生任何变化
所以 代码就可写出了：
def find_root(x): while x!=parent[x]: x=parent[x] return x def union(x,y): x_root=find_root(x) y_root=find_root(y) parent[x_root]=y_root n,m,p=map(int,input().strip().split()) parent=[i for i in range(n+1)]#初始化 for i in range(m):#h合并 tmp=list(map(int,input().strip().split())) union(tmp[0],tmp[1]) for j in range(n):#判断 tmp=list(map(int,input().strip().split())) if find_root(tmp[0])==find_root(tmp[1]): print('Yes') else: print('No')
