<jupyter_start><jupyter_text>Графы * взвешенный - может быть несколько разных цен* невзвешенные * направленные - которые есть направление между вершинами* ненаправленные  graph representation * список ребер (edge list)    * это список из идентификаторов А и Б и из весов    * * список смежности (adjecency list)    * для каждой вершины - список соседей храним* матрица смежности (adjecency matris) степень вершины - сколько выходит ребер.Входная - сколько входитвыходная - сколько выходитN - вершины M-ребер<jupyter_code>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<jupyter_output>2<jupyter_text>defaultdict - полезная штука<jupyter_code>from collections import defaultdict
d = defaultdict(int)
d['test'] += 1
d<jupyter_output><empty_output><jupyter_text>adjecency list<jupyter_code>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 []<jupyter_output><empty_output><jupyter_text>adjecency matrix 0 и 1 ставим на пересечении колонки и строки вершин<jupyter_code>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<jupyter_output><empty_output><jupyter_text>Depth first search кратчайший путь на невзвешенных графах * идем туда, где не были* если оказываемя где были, возвращаемся назад - для каждой комнаты помним<jupyter_code>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)<jupyter_output><empty_output><jupyter_text>компонент связности - все вершины из всех достижимы.dfs не обойдет все сложность - Vertex + Edges  оптимально как список смежности если заменить на список ребер - будет сложность как Vertex*Edgesесли заменить на список ребер - будет сложность как Vertex^2  алгоритм поиска уровня связности<jupyter_code>counter = 0

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

print(counter)<jupyter_output>3<jupyter_text>BFS<jupyter_code>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)<jupyter_output>[1, 2, 3]
{'fraction_non_alphanumeric': 0.1228177641653905, 'fraction_numerical': 0.012557427258805513, 'mean_word_length': 3.567832167832168, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 26, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '7', 'dir': 'jupyter-structured-clean-dedup', 'id': '142304', 'license': 'MIT', 'n_tokens_mistral': 1293, 'n_tokens_neox': 1334, 'n_words': 330, 'path': '02 Algorithms/Lecture 2.ipynb', 'repo_name': 'ksetdekov/HSE_DS', 'size': '3265'}