Статья Автор: Ратькин Иван

7

def BFS(g,s):
    visited=[False]*n
    k=0
    queue=[s]
    visited[s]=True
    while queue:
        v=queue.pop(0)
        for nxt in g[v]:
            if not visited[nxt]:
                visited[nxt]=True
                queue.append(nxt)
                k+=1
    return k
n,m=map(int,input().split())
g=list([] for _ in range(n))
for i in range(m):
    a,b=map(int,input().split())
    g[a-1].append(b-1)
k=0
for i in range(n):
    k+=BFS(g,i)
print(k+n)
Загрузка...
Чтобы оставить комментарий, необходимо авторизоваться
💬
Пока нет комментариев. Будьте первым!
Печать