Day 166-Q4 — 2026-09-30 | DAG の最小パス被覆（頂点を共有してよい版）

📋 コピーimport sys
def main():
    data = sys.stdin.buffer.read().split()
    n, m = int(data[0]), int(data[1])
    adj = [0]*n
    for k in range(m):
        a = int(data[2+2*k])-1; b = int(data[3+2*k])-1
        adj[a] |= 1 << b
    # 推移閉包（DAG なので、トポロジカル逆順に reach[v] = adj[v] | OR reach[w]）
    indeg = [0]*n
    for v in range(n):
        x = adj[v]
        while x:
            lb = x & -x; indeg[lb.bit_length()-1] += 1; x ^= lb
    order = []; st = [v for v in range(n) if indeg[v] == 0]
    while st:
        v = st.pop(); order.append(v)
        x = adj[v]
        while x:
            lb = x & -x; w = lb.bit_length()-1; x ^= lb
            indeg[w] -= 1
            if indeg[w] == 0: st.append(w)
    reach = [0]*n
    for v in reversed(order):
        r = adj[v]; x = adj[v]
        while x:
            lb = x & -x; r |= reach[lb.bit_length()-1]; x ^= lb
        reach[v] = r
    # 閉包上の二部マッチング（Kuhn、ビット集合で未訪問の右頂点だけを見る）
    matchR = [-1]*n
    sys.setrecursionlimit(10000)
    def try_(u, vis):
        cand = reach[u] & ~vis[0]
        while cand:
            lb = cand & -cand; w = lb.bit_length()-1
            vis[0] |= lb
            if matchR[w] < 0 or try_(matchR[w], vis):
                matchR[w] = u; return True
            cand = reach[u] & ~vis[0]
        return False
    mt = 0
    for u in range(n):
        if try_(u, [0]): mt += 1
    print(n - mt)
main()