Day 164-Q4 — 2026-10-02 | 橋をなくすために足す辺の最小数（橋木の葉の数 L に対し ⌈L/2⌉。再帰なしの lowlink と、多重辺でも壊れない親辺の判定）

📋 コピーimport sys


def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    g = [[] for _ in range(n)]          # (隣接頂点, 辺番号)
    for i in range(m):
        u, v = int(data[2 + 2 * i]) - 1, int(data[3 + 2 * i]) - 1
        g[u].append((v, i))
        g[v].append((u, i))
    # 橋を探す（再帰なしの lowlink）
    order = [-1] * n
    low = [0] * n
    is_bridge = [False] * m
    t = 0
    stack = [(0, -1, 0)]                # (頂点, 親へ来た辺番号, 次に見る隣接の位置)
    order[0] = low[0] = 0
    t = 1
    while stack:
        u, pe, idx = stack.pop()
        if idx < len(g[u]):
            stack.append((u, pe, idx + 1))
            v, e = g[u][idx]
            if e == pe:                 # 来た辺そのものは戻らない（辺番号で判定。多重辺があっても正しい）
                continue
            if order[v] == -1:
                order[v] = low[v] = t
                t += 1
                stack.append((v, e, 0))
            elif order[v] < low[u]:
                low[u] = order[v]
        elif pe != -1:
            # u の探索が終わった。親 p へ low を伝え、橋かどうか決める
            p = None
            for v, e in g[u]:
                if e == pe:
                    p = v
                    break
            if low[u] < low[p]:
                low[p] = low[u]
            if low[u] > order[p]:
                is_bridge[pe] = True
    # 橋を除いた連結成分（2 辺連結成分）に番号を振る
    comp = [-1] * n
    c = 0
    for s in range(n):
        if comp[s] != -1:
            continue
        comp[s] = c
        st = [s]
        while st:
            u = st.pop()
            for v, e in g[u]:
                if not is_bridge[e] and comp[v] == -1:
                    comp[v] = c
                    st.append(v)
        c += 1
    # 橋木での次数。葉（次数 1）の数 L に対して答えは ceil(L/2)
    deg = [0] * c
    for u in range(n):
        for v, e in g[u]:
            if is_bridge[e]:
                deg[comp[u]] += 1
    leaves = sum(1 for d in deg if d == 1)
    print((leaves + 1) // 2)


main()