ABC264E - Blackout 2

考え方

「辺を切る問題」は，逆順に考えて「辺をつなぐ問題」に読み替える事を考えると，UnionFind（UnionFind木 - 競プロはじめました）が使える．

UnionFindの初期化では，

• すべての発電所をつなぐ
• イベントで切られない辺をつなぐ

とすればよい．

回答例

N, M, E = map(int, input().split())
edge = []
for i in range(E):
    u, v = map(lambda x: int(x), input().split())
    edge.append((u, v))

Q = int(input())
X = list(int(input()) for _ in range(Q))
setX = set(X)

# --- UnionFind ---
p = [-1] * (N + M + 1)
def root(x):
  if p[x] < 0:
    return x
  p[x] = root(p[x])
  return p[x]
 
def unite(x, y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  p[x] += p[y]
  p[y] = x

def size(x):
  x = root(x)
  return -p[x]
# --- UnionFind ---

for i in range(N + 1, N + M):
    unite(i, i + 1)

for i, (u, v) in enumerate(edge):
    if i + 1 not in setX:
        unite(u, v)

ans = [size(N + 1) - M]
for x in X[::-1]:
    u, v = edge[x - 1]
    unite(u, v)
    ans.append(size(N + 1) - M)

print(*ans[-2::-1], sep = '\n')