ABC229E - Graph Destruction

【関連記事】

• UnionFind木 - 競プロはじめました

考え方

逆から考えてUnionFind木でつないでいくだけ．

連結成分の数は，

• 頂点を加えたら+1
• つながっていないグループを新たにつないだら-1

とすればよい．

グラフの辺は小さい頂点から大きい頂点に向かってのみ張るようにしないと，まだ考えていない頂点をつないでしまうので注意．

回答例

N, M = map(int, input().split())
G = [[] for _ in range(N)]
for _ in range(M):
  a, b = map(int, input().split())
  a -= 1
  b -= 1
  if b < a:
    a, b = b, a
  G[a].append(b)
  
p = [-1] * N
def root(x):
  if p[x] < 0:
    return x
  p[x] = root(p[x])
  return p[x]
 
def merge(x, y):
  x = root(x)
  y = root(y)
  if x == y:
    return
  p[y] = x  

num = 0
ans = [0]
for v in range(N - 1, 0, -1):
  num += 1
  for w in G[v]:
    if root(v) != root(w):
      num -= 1
    merge(v, w)
  ans.append(num)
  
ans.reverse()  
print(*ans, sep = '\n')