# ---
# jupyter:
#   jupytext:
#     text_representation:
#       extension: .py
#       format_name: light
#       format_version: '1.5'
#       jupytext_version: 1.14.4
#   kernelspec:
#     display_name: Python 3
#     language: python
#     name: python3
# ---

# # Графы

# * взвешенный - может быть несколько разных цен
# * невзвешенные

# * направленные - которые есть направление между вершинами
# * ненаправленные

# ### graph representation

# * список ребер (edge list)
#     * это список из идентификаторов А и Б и из весов
#     * 
# * список смежности (adjecency list)
#     * для каждой вершины - список соседей храним
# * матрица смежности (adjecency matris)

# степень вершины - сколько выходит ребер.
#
# Входная - сколько входит
#
# выходная - сколько выходит
#
# N - вершины M-ребер
#
#

# +
n, m = list(map(int, input().split()))
edges = []

for i in range(m):
    v_from, v_to = list(map(int, input(), split()))
    edge.append((v_from, v_to))
    
    
def get_neighbours(v, edges):
    neighbours = []
    for edge in edges:
        if edge[0] ==v:
            neighbours.append(edge[1])
    return neighbours


# -

# ### defaultdict - полезная штука

from collections import defaultdict

d = defaultdict(int)
d['test'] += 1
d

# ### adjecency list

# +
from collections import defaultdict
n, m = list(map(int, input().split()))
graph = defaultdict(list)

for i in range(m):
    v_from, v_to = list(map(int, input(), split()))
    graph[v_from].append(v_to)
    
    
def get_neighbours(v, graph):
    if v in graph:
        return graph[v]
    return []


# -

# ### adjecency matrix

# 0 и 1 ставим на пересечении колонки и строки вершин

# +
n, m = list(map(int, input().split()))
edges = [[0 for i in range(n)] for j in range(n)]

for i in range(m):
    v_from, v_to = list(map(int, input(), split()))
    graph[v_from][v_to] = 1
    
    
def get_neighbours(v, edges):
    neighbours = []
    for i in range (leng(graph)):
        if graph[v][i] == 1:
            neighbours.append(i)
    return neighbours


# -

# # Depth first search

# кратчайший путь на невзвешенных графах

# * идем туда, где не были
# * если оказываемя где были, возвращаемся назад - для каждой комнаты помним

# +
graph = [[1, 2, 3], [0, 4], [0], [0, 4], [1,3], [5], [6]] # список смежности

n = len(graph)
visited = [False for i in range(n)]

def dfs(v):
    visited[v] = True
    
    for u in graph[v]:
        if not visited[u]:
            dfs(u)


# -

# компонент связности - все вершины из всех достижимы.
#
# dfs не обойдет все

# сложность - Vertex + Edges

# #### оптимально как список смежности

# если заменить на список ребер - будет сложность как Vertex*Edges
# если заменить на список ребер - будет сложность как Vertex^2

# ### алгоритм поиска уровня связности

# +
counter = 0

for k in range(n):
    if not visited[k]:
        counter += 1
        dfs(k)

print(counter)
# -

# # BFS

# +
from collections import deque
graph = [[1, 2, 3], [0, 4], [0], [0, 4], [1,3], [5], [6]] # список смежности

n = len(graph)
visited = [False for i in range(n)]
def bfs(start):
    print(start)
    q = deque()
    q.append(start)
    visited[start] = True
    while len(q) !=0:
        v = q.popleft()
        for u in graph[v]:
            if not visited[u]:
                
                visited[u] = True
                q.append(u)

# -



StarcoderdataJupyterScriptsDedupFiltered