并查集练习_战争中的城市
作者:
成理第一深情
,
2024-04-30 20:28:00
,
所有人可见
,
阅读 8
"""
思路:
1、存下所有的路
2、如果路径上的两个点都不包含被侵占的点,说明这两个点之间本身就有路
3、最后统计一下集合的数量
4、要让所有路集合连通,就需要建至少集合数量减1的路
"""
import sys
sys.setrecursionlimit(1000000)
input = sys.stdin.readline
def find(x):
if x != p[x]:
p[x] = find(p[x])
return p[x]
n, m, k = map(int, input().strip().split())
road = []
for i in range(m):
a, b = map(int, input().strip().split())
road.append([a, b])
important = list(map(int, input().strip().split())) # 输入重点关注的城市
for x in important:
p = [i for i in range(n + 1)]
for i in range(m):
a, b = road[i]
if a != x and b != x:
pa = find(a)
pb = find(b)
p[pa] = pb
# 统计集合的个数
cnt = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
if i != x:
cnt[find(i)] += 1
res = 0
for x in cnt:
if x != 0:
res += 1
print(res - 1)