Python之并查集洛谷蓝桥杯

同时正在备战蓝桥杯 题解如有不足请多批评指正  

大一双非本科在读

目标是进大厂 

洛谷&＃xff1a;亲戚关系 题目链接

问题分析&＃xff1a;这是一道考察并查集的经典例题。

何为并查集&＃xff1f;并查集是一种&＃xff08;树型&＃xff09;数据结构 &＃xff0c;用于处理一些不相交集合的合并及查询问题。

思想&＃xff1a;用一个数组表示了整片森林&＃xff0c;树的根节点唯一标识了一个集合&＃xff0c;我们只要找到了某个元素的的树根&＃xff0c;就能确定它在哪个集合里。

例如给出数组parent&＃61;[0,1,5,1,3,1]&＃xff0c;parent[i]代表结点i的父结点&＃xff08;很形象吧&＃xff01;&＃xff1f;&＃xff09;

观察数组&＃xff0c;我们知道:parent[2]&＃61;5 &＃xff0c;说明了结点2的父节点是5

再来&＃xff1a;parent[5]&＃61;1&＃xff0c;说明了结点5的父节点是1

再来:parent[1]&＃61;1,说明了结点1的父节点是1

对上面这行可能有疑惑&＃xff1a;我们先记住&＃xff0c;若parent[i]&＃61;i  则i是一个集合内的根节点

那么他有什么作用&＃xff1a;如果一个结点j 它的父节点的父节点的父节点的父节点.....是i

说明了j和它的父节点和它的父节点的父节点和....一共这么多结点&＃xff0c;对于每一个结点&＃xff0c;都可以访问到i结点。我们不如把它叫做祖先&＃xff08;能够访问 类似于 含有血缘关系&＃xff0c;你和你的祖先&＃xff0c;你的父亲的祖先&＃xff0c;你的父亲的父亲的祖先都有血缘关系。&＃xff09;

因此这么多结点就构成了一个集合&＃xff08;代表集合的对象是根节点&＃xff08;祖先&＃xff09;&＃xff09;

所以对于刚刚提到的数组&＃xff0c;由于结点5可以访问到祖先>>1&＃xff0c;所以5和1有血缘关系&＃xff0c;即5属于祖先1代表的集合&＃xff0c;由于结点2的父节点是5&＃xff0c;所以它可以通过父节点5访问到祖先>>1&＃xff0c;所以2和1有血缘关系&＃xff0c;即2属于祖先1代表的集合。

因此我们要判断两个结点是否属于同一个集合&＃xff0c;可以借助访问各自的祖先加以判断。

如果祖先相同&＃xff0c;那么属于同一集合&＃xff0c;否则不属于同一集合。

对于上述数组结点0和结点1就不属于同一集合

所以下面给出访问祖先的代码:&＃xff08;关于优化下面会阐述&＃xff09;

def find_root(x):while x!&＃61;parent[x]:3如果不是祖先 就访问自己的父节点x&＃61;parent[x]return x

 那么上面这段代码就是代表了并查集的思想之一&＃xff1a;查询

那么下面我们研究并查集的另一个思想&＃xff1a;合并

再次给出上面那个例子parent&＃61;[0,1,5,1,3,1]

我们知道结点1&＃xff0c;2&＃xff0c;3&＃xff0c;4&＃xff0c;5同属于一个集合&＃xff08;用结点1来标识&＃xff09;

由于parent[0]&＃61;0 说明0是一个集合的祖先&＃xff0c;这个集合用结点0来标识

由于以结点0为代表的集合元素个数为1&＃xff0c;比较特殊&＃xff0c;我们不妨给他&＃xff08;集合&＃xff09;添加两个结点

分别是结点6&＃xff0c;结点7&＃xff0c;因此parent&＃61;[0,1,5,1,3,1,0,0]

所以现在 结点0&＃xff0c;6&＃xff0c;7同属于一个集合&＃xff08;用结点0来标识&＃xff09;

下面研究合并&＃xff0c;何为合并&＃xff1f;就是将两个集合变为为一个集合

容易想到&＃xff0c;我们可以把结点0&＃xff08;祖先&＃xff09;作为结点1的子结点&＃xff0c;换句话说&＃xff0c;把结点1作为结点0的父节点。

那么这样子有什么用&＃xff1a;我们知道用结点0来标识的集合中的结点&＃xff0c;都可以访问到结点0&＃xff0c;现在结点0又可以访问到结点1&＃xff0c;所以用结点0来标识的集合中的结点&＃xff0c;都可以访问到结点1&＃xff0c;因此用结点1来标识的集合 结点数目扩大了&＃xff01; 这不正达到了我们想要的效果吗&＃xff1f;

简言之 集合A和集合B原本分属两大家族&＃xff0c;把A的祖先作为B祖先的孩子&＃xff0c;因而集合A和B中的所有结点都有了血缘关系&＃xff0c;实现了家族合并。

 所以下面给出合并的代码&＃xff1a;

def union(x,y):#合并x_root,y_root&＃61;find(x),find(y)parent[x_root]&＃61;y_root#一般的x_root!&＃61;y_root&＃xff0c;直接合并过去#如果x_root&＃61;y_root,合并本身&＃xff0c;没有发生任何变化


 所以 代码就可写出了&＃xff1a;

def find_root(x):while x!&＃61;parent[x]:x&＃61;parent[x]return xdef union(x,y):x_root&＃61;find_root(x)y_root&＃61;find_root(y)parent[x_root]&＃61;y_rootn,m,p&＃61;map(int,input().strip().split())parent&＃61;[i for i in range(n&＃43;1)]#初始化for i in range(m):#h合并tmp&＃61;list(map(int,input().strip().split()))union(tmp[0],tmp[1])for j in range(n):#判断tmp&＃61;list(map(int,input().strip().split()))if find_root(tmp[0])&＃61;&＃61;find_root(tmp[1]):print(&＃39;Yes&＃39;)else:print(&＃39;No&＃39;)

 但是这样超时 所以需要进行优化&＃xff1a;

先分析超时的原因&＃xff1a;还是利用上面给出的数组parent&＃61;[0,1,5,1,3,1,0,0]&＃xff08;未合并&＃xff09;

我们可以画出下面这样的关系图&＃xff1a;

 所以科学家们给出了一种方法&＃xff1a;路径压缩。

简言之&＃xff0c;对于上图&＃xff0c;比如在访问4的根节点的时候&＃xff0c;经过图中标识的&＃39;&＃39;很长&＃39;&＃39;一段路径&＃xff0c;这一段路径由许许多多的结点构成&＃xff0c;它们有一个共同特点就是根节点都是1&＃xff0c;那么路径压缩要做的就是把这条路径上的所有结点的父节点设为结点1

这样子的作用&＃xff1a;比如我下一次查询结点3的根节点的时候&＃xff0c;只需要1次&＃xff0c;原来需要9999次&＃xff01;

def find_root(x):#返回根节点if x!&＃61;parent[x]:#只要不是根节点parent[x]&＃61;find_root(parent[x])#修改父节点为根结点return parent[x]#返回根节点(父节点)

 第一次接触路径压缩如果不太好理解&＃xff0c;可以先和小郑一样把这个模板记下来~


n,m,p&＃61;map(int,input().strip().split())parent&＃61;[i for i in range(n&＃43;1)]def find_root(x):#返回根节点if x!&＃61;parent[x]:#只要不是根节点parent[x]&＃61;find_root(parent[x])#把x的父节点设为根节点return parent[x]def union(x,y):x_root&＃61;find_root(x)y_root&＃61;find_root(y)parent[x_root]&＃61;y_rootfor i in range(m):tmp&＃61;list(map(int,input().strip().split()))union(tmp[0],tmp[1])for j in range(p):tmp&＃61;list(map(int,input().strip().split()))if find_root(tmp[0])&＃61;&＃61;find_root(tmp[1]):print(&＃39;Yes&＃39;)else:print(&＃39;No&＃39;)


 可见路径压缩帮助我们优化了算法

蓝桥杯真题实战&＃xff1a;七段码&＃xff08;第十一届试题E填空压轴&＃xff09;>>考察并查集

代码设计分析:题目就是在问一个连通性问题&＃xff0c;从7条边选几个出来判断是不是连通图。

也就是判断是不是属于同一个集合的问题。首先明确一点&＃xff0c;并查集两大功能&＃xff1a;查找与合并。要先合并&＃xff0c;再查找&＃xff08;没有合并一个集合那拿什么来查找&＃xff1f;&＃xff09;。所以&＃xff0c;相当于我们要先构建亲戚关系网&＃xff0c;最后判断所有结点的祖先是否都是同一个&＃xff0c;如果是则连通&＃xff0c;否则不连通。

那么构建亲戚关系的条件&＃xff1a;如果两个顶点直接相连&＃xff0c;那么把那个点所属的集合与另外一个点所属的集合合并。当所有的点合并完了&＃xff0c;只需要遍历所有的点的祖先&＃xff0c;判断是否都是同一个&＃xff0c;如果是&＃xff0c;大功告成&＃xff0c;count加1

def find_root(x):if x!&＃61;parent[x]:parent[x]&＃61;find_root(parent[x])return parent[x]def union(x,y):x_root,y_root&＃61;find_root(x),find_root(y)if x_root!&＃61;y_root:parent[x_root]&＃61;y_rootedge&＃61;[[0]*7 for i in range(7)]#设一个0号进去&＃xff0c;无边与其相连l&＃61;[0,1,2,3,4,5,6]
edge[0][1]&＃61;edge[0][2]&＃61;edge[1][3]&＃61;edge[1][4]&＃61;edge[2][3]&＃61;1
edge[3][4]&＃61;edge[3][5]&＃61;edge[4][6]&＃61;edge[5][6]&＃61;edge[2][5]&＃61;1#有边相连记作1for i in range(7):for j in range(7):edge[i][j]&＃61;max(edge[i][j],edge[j][i])#无向图对称import itertoolscount&＃61;0for i in range(1,8):#灯泡数目for j in itertools.combinations(l,i):#比如[(1,2,3),[1,2,4]]parent&＃61;[i for i in range(7)]#判断两两是否连通for k in range(0,i):for p in range(k&＃43;1,i):if edge[j[k]][j[p]]&＃61;&＃61;1:#如果连通&＃xff0c;合并union(j[k],j[p])for m in range(i-1):#判断属于是否同一集合&＃xff08;最终所有的&＃xff09;if find_root(j[m])!&＃61;find_root(j[m&＃43;1]):breakelse:print(j)#显示符合条件的数据&＃xff0c;可删去count&＃43;&＃61;1
print(count)
#答案80

 我是小郑 正在奔赴热爱 奔赴山海&＃xff01;