第十五届蓝桥杯Python大学B组国赛I题题解

本文主要是介绍第十五届蓝桥杯Python大学B组国赛I题题解，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

大概题目

某国王要给n个岛之间修桥，桥是双向的，国王可以将a岛和b岛连接起来，也可以将两座岛的桥炸掉，国王想知道经过一系列操作之后两座岛之间是否连接。

输入：岛屿数量n，每行第一个数是选择，1 是合并，然后再输入两个岛屿a和b，输入 2 是炸掉最近一次合并的桥，如果没有桥就不需要任何操作，后面不需要岛屿a和b，如果输入 3 进行查询a与b是否相连。输入不是1,2,3则结束。

输出：两座岛是否连接，“ Yes ” or “ No ”。

输入样例:

输出样例:

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