Day 165-Q4 — 2026-09-29 | 強連結にするために足す最小の辺数（縮約 DAG の始点数と終点数の最大）

📋 コピーimport sys
def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    adj = [[] for _ in range(n)]
    es = []
    for i in range(m):
        u = int(data[2 + 2 * i]) - 1; v = int(data[3 + 2 * i]) - 1
        adj[u].append(v); es.append((u, v))
    # 反復版 Tarjan で強連結成分に分ける
    idx = [-1] * n; low = [0] * n; onst = [False] * n; comp = [-1] * n
    st = []; cnt = 0; nc = 0
    for s in range(n):
        if idx[s] != -1: continue
        stack = [(s, 0)]; idx[s] = low[s] = cnt; cnt += 1; st.append(s); onst[s] = True
        while stack:
            v, i = stack[-1]
            if i < len(adj[v]):
                stack[-1] = (v, i + 1); w = adj[v][i]
                if idx[w] == -1:
                    idx[w] = low[w] = cnt; cnt += 1; st.append(w); onst[w] = True
                    stack.append((w, 0))
                elif onst[w] and idx[w] < low[v]:
                    low[v] = idx[w]
            else:
                stack.pop()
                if stack:
                    u = stack[-1][0]
                    if low[v] < low[u]: low[u] = low[v]
                if low[v] == idx[v]:
                    while True:
                        w = st.pop(); onst[w] = False; comp[w] = nc
                        if w == v: break
                    nc += 1
    if nc == 1:
        print(0); return
    indeg = [0] * nc; outdeg = [0] * nc
    for u, v in es:
        if comp[u] != comp[v]:
            outdeg[comp[u]] += 1; indeg[comp[v]] += 1
    src = sum(1 for c in range(nc) if indeg[c] == 0)     # 入る辺が無い成分
    snk = sum(1 for c in range(nc) if outdeg[c] == 0)    # 出る辺が無い成分
    print(max(src, snk))
main()