Статья Автор: Дубинин Дмитрий

Посчитать для каждой вершины, сколько вершин достижимо из неё (включая саму себя), и просуммировать эти количества

n, m = map(int, input().split())
graph = [[] for _ in range(n)]

for _ in range(m):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)

result = 0

for start in range(n):
    visited = [False] * n
    stack = [start]
    visited[start] = True
    count = 1
    
    while stack:
        v = stack.pop()
        for to in graph[v]:
            if not visited[to]:
                visited[to] = True
                count += 1
                stack.append(to)
    
    result += count

print(result)

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать