ABC288C - Don’t be cycle

考え方

辺を順番に見ていき，閉路でないならつなぐ．つなげない辺の数をカウントすれば良い．
閉路検出 - 競プロはじめました

アライグマ「ABC288だったのだ！　C問題は、「辺0本から始めて、閉路にならないように何本追加できるか」だと思うと、閉路にならないように貪欲に辺を追加するのが最適なのだ！　Union-findで同じグループの頂点を結ばないようにチェックすればいいのだ！」

— 競技プログラミングをするフレンズ (@kyopro_friends) February 4, 2023

回答例（UnionFind）

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

N, M = map(int, input().split())
E = []
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    E.append((a, b))
# ------------------
p = [-1] * (N + 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]
# ------------------
cnt = 0
for a, b in E:
    if root(a) != root(b):
        unite(a, b)
    else:
        cnt += 1

print(cnt)