本文主要是介绍第十五届蓝桥杯Python大学B组国赛I题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
大概题目
某国王要给n个岛之间修桥，桥是双向的，国王可以将a岛和b岛连接起来，也可以将两座岛的桥炸掉，国王想知道经过一系列操作之后两座岛之间是否连接。
输入：岛屿数量n，每行第一个数是选择，1 是 合并，然后再输入两个岛屿a和b，输入 2 是炸掉最近一次合并的桥，如果没有桥就不需要任何操作，后面不需要岛屿a和b，如果输入 3 进行查询a与b是否相连。输入不是1,2,3则结束。
输出：两座岛是否连接，“ Yes ” or “ No ”。
输入样例:
5
1 2 3
1 3 4
2
3 3 4
1 2 5
3 3 5
4
输出样例:
No
Yes
可撤销并查集可以做，但是为了简便直接利用python的特性（可以直接将每个合并操作之后的父数组保存）
思路：
用一个数组 st 记录父类数组 f 的值，每一次合并操作就将新的父类数组添加到st中，然后是 2 删除操作就将st最后一个删除，然后将新的最后一个值赋值给父类 f，然后其他就用并查集板子就行了。
st.append(string(str(f)))
为什么在添加f的时候用了一个str操作：
st不能直接用append(f)，这样会导致更改f，st里面所有的都会变
写了一个string函数，将字符串化的f转为一个列表，这样就不会影响st前面的值了
def string(s):lt=[]for i in range(1,len(s),3):lt.append(int(s[i]))return lt
全部代码：
n = int(input())
f = [0] + [i for i in range(1, n + 1)]def string(s):lt=[]for i in range(1,len(s),3):lt.append(int(s[i]))return lt
st=[string(str(f))]
def find(a):if f[a] == a:return af[a] = find(f[a])return f[a]
def unit(a, b):x = find(a)y = find(b)f[x] = y
while True:s=input()o=int(s[0])if o == 1:a=int(s[2]);b=int(s[4])unit(a, b)st.append(string(str(f)))elif o == 2:if len(st)>1:st.pop()f=st[-1]elif o == 3:a = int(s[2])b = int(s[4])x = find(a)y = find(b)if x == y:print('Yes')else:print('No')else:break这篇关于第十五届蓝桥杯Python大学B组国赛I题题解的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
