但是这样超时 所以需要进行优化：
先分析超时的原因：还是利用上面给出的数组parent=[0,1,5,1,3,1,0,0]（未合并）
我们可以画出下面这样的关系图：
所以科学家们给出了一种方法：路径压缩。
简言之，对于上图，比如在访问4的根节点的时候，经过图中标识的''很长''一段路径，这一段路径由许许多多的结点构成，它们有一个共同特点就是根节点都是1，那么路径压缩要做的就是把这条路径上的所有结点的父节点设为结点1
这样子的作用：比如我下一次查询结点3的根节点的时候，只需要1次，原来需要9999次！
def find_root(x):#返回根节点 if x!=parent[x]:#只要不是根节点 parent[x]=find_root(parent[x])#修改父节点为根结点 return parent[x]#返回根节点(父节点)
第一次接触路径压缩如果不太好理解，可以先和小郑一样把这个模板记下来~
n,m,p=map(int,input().strip().split()) parent=[i for i in range(n+1)] def find_root(x):#返回根节点 if x!=parent[x]:#只要不是根节点 parent[x]=find_root(parent[x])#把x的父节点设为根节点 return parent[x] def union(x,y): x_root=find_root(x) y_root=find_root(y) parent[x_root]=y_root for i in range(m): tmp=list(map(int,input().strip().split())) union(tmp[0],tmp[1]) for j in range(p): tmp=list(map(int,input().strip().split())) if find_root(tmp[0])==find_root(tmp[1]): print('Yes') else: print('No')
可见路径压缩帮助我们优化了算法
蓝桥杯真题实战：七段码（第十一届试题E填空压轴）>>考察并查集
代码设计分析:题目就是在问一个连通性问题，从7条边选几个出来判断是不是连通图。
也就是判断是不是属于同一个集合的问题。首先明确一点，并查集两大功能：查找与合并。要先合并，再查找（没有合并一个集合那拿什么来查找？）。所以，相当于我们要先构建亲戚关系网，最后判断所有结点的祖先是否都是同一个，如果是则连通，否则不连通。
那么构建亲戚关系的条件：如果两个顶点直接相连，那么把那个点所属的集合与另外一个点所属的集合合并。当所有的点合并完了，只需要遍历所有的点的祖先，判断是否都是同一个，如果是，大功告成，count加1
def find_root(x): if x!=parent[x]: parent[x]=find_root(parent[x]) return parent[x] def union(x,y): x_root,y_root=find_root(x),find_root(y) if x_root!=y_root: parent[x_root]=y_root edge=[[0]*7 for i in range(7)]#设一个0号进去，无边与其相连 l=[0,1,2,3,4,5,6] edge[0][1]=edge[0][2]=edge[1][3]=edge[1][4]=edge[2][3]=1 edge[3][4]=edge[3][5]=edge[4][6]=edge[5][6]=edge[2][5]=1#有边相连记作1 for i in range(7): for j in range(7): edge[i][j]=max(edge[i][j],edge[j][i])#无向图对称 import itertools count=0 for i in range(1,8):#灯泡数目 for j in itertools.combinations(l,i):#比如[(1,2,3),[1,2,4]] parent=[i for i in range(7)] #判断两两是否连通 for k in range(0,i): for p in range(k+1,i): if edge[j[k]][j[p]]==1:#如果连通，合并 union(j[k],j[p]) for m in range(i-1):#判断属于是否同一集合（最终所有的） if find_root(j[m])!=find_root(j[m+1]): break else: print(j)#显示符合条件的数据，可删去 count+=1 print(count)
#答案80
我是小郑 正在奔赴热爱 奔赴山海！
