Submission #39432647

---

Source Code Expand

"""
a->b->c->dのとき
a->cが必要。そうなるとa->dも必要になる。
aからたどれる全部の頂点に結局エッジが必要になる。
こたえ
頂点ごとのたどれる個数-最初からあるエッジの個数
"""
from collections import defaultdict

graph = defaultdict(list)

def find_child_size(root):
    visited = set()
    visited.add(root)
    children = graph[root].copy()
    while len(children):
        c = children.pop()
        if c not in visited:
            visited.add(c)
            children.extend(graph[c])
    return len(visited) - 1

def main():
    N, M = map(int, input().split())

    for i in range(M):
        u, v = map(int, input().split())
        graph[u].append(v)
    
    total = 0
    for root in range(1, N+1):
        cs = find_child_size(root)
        total += cs - len(graph[root])

    print(total)

main()

Submission Info

Judge Result