AcWing 1485. 战争中的城市(python)
原题链接
中等
作者:
柠檬茶去冰
,
2024-12-15 16:41:42
,
所有人可见
,
阅读 2
import sys
def find(x):
if p[x]!=x:
p[x]=find(p[x])
return p[x]
def union(x,y):
px=find(x)
py=find(y)
if px!=py: #按秩合并优化性能
if size[px]>size[py]:
p[py]=px
elif size[px]<size[py]:
p[px]=py
else:
p[py]=px
size[px]+=1
def main(n,m,roads,att):
global p,size
ans=[]
for i in att:
p =list(range(n+1)) #初始化,防止每一次计算有多少个集合时相互干扰
size = [1] * (n + 1)
for a,b in roads:
if a!=i and b!=i:
union(a,b)
components=set()
for j in range(1,n+1): #遍历为了看去掉攻陷的城市后有多少个集合
if j!=i:
components.add(find(j)) #每添加进去说明有一个集合
ans.append(len(components)-1) #长度就是有集合的个数,减1,就是连通要的线
return ans
n,m,k=map(int,sys.stdin.readline().split())
p=[]
size=[]
roads=[tuple(map(int,sys.stdin.readline().split())) for _ in range(m)]
att=list(map(int,sys.stdin.readline().split()))
ans=main(n,m,roads,att)
for i in ans:
print(i)