Граф как модель

Граф обычно рисуют кружками и линиями, и от этого кажется, что он про геометрию. Это не так.

Граф — это множество объектов и отношение между ними. Объекты называют вершинами, отношение — рёбрами. Где именно нарисованы кружки, значения не имеет: важно только, кто с кем соединён.

Поэтому графом оказывается почти всё, где есть слово «связаны»:

Последняя строка важна: поле из прошлого занятия — тоже граф, просто заданный не списком рёбер, а правилом «соседние клетки соединены». Значит всё, что мы дальше научимся делать с графами, будет работать и на поле.

Ориентированный или нет

Если отношение симметрично — «соединены дорогой», «знакомы», — граф неориентированный, и ребро принадлежит обеим вершинам сразу.

Если нет — «ведёт ссылка», «должен быть сдан раньше» — граф ориентированный, и ребро идёт из одной вершины в другую.

Различить их надо до написания кода: от этого зависит, сколько раз ребро попадёт в структуру.

Способов три, и выбор между ними — не вкусовщина, а расчёт.

Список рёбер

Просто список пар. Занимает $O(m)$ памяти, но ответить «кто соседи вершины 5» можно только полным перебором. Годится, когда рёбра нужны все сразу и по одному разу.

Матрица смежности

Таблица $n \times n$, где на пересечении стоит единица, если ребро есть.

linked = [[0] * (n + 1) for _ in range(n + 1)]
linked[a][b] = linked[b][a] = 1

Проверка «есть ли ребро» — мгновенная. Но памяти нужно $O(n^2)$: при $n = 2 \cdot 10^5$ это сорок миллиардов ячеек, то есть матрица просто не существует. Матрица применима, только когда вершин мало — скажем, несколько сотен.

Список смежности

Для каждой вершины — список её соседей. Памяти $O(n + m)$, перебрать соседей можно за их количество.

adj = [[] for _ in range(n + 1)]
for _ in range(m):
    a, b = map(int, input().split())
    adj[a].append(b)
    adj[b].append(a)      # неориентированный граф — обе стороны!

Это основной способ, и почти все задачи о графах решаются с ним. Обратите внимание на вторую строку внутри цикла: в неориентированном графе ребро надо положить в обе ячейки. Забыть её — самая частая ошибка темы, и программа при этом не падает.

Список делается на $n + 1$ ячейку, чтобы вершина с номером $n$ имела своё место и не приходилось всюду вычитать единицу.

В графе 200 000 вершин и 200 000 рёбер. Каким способом его хранить?

Степень вершины — количество выходящих из неё рёбер. В списке смежности это просто длина её списка.

Из определения сразу следует утверждение, которое стоит понимать, а не запоминать:

Каждое ребро имеет два конца и потому прибавляет единицу ровно к двум степеням. Значит сумма всех степеней вдвое больше числа рёбер — всегда, в любом графе.

Это отличная проверка себя. Посчитали степени, сложили, получили не $2m$ — значит где-то ребро учтено один раз вместо двух. Ошибка найдена до отправки решения.

Что видно по степеням

Многие вопросы решаются степенями без всякого обхода. Например, сколько в графе путей длины два: такой путь однозначно задаётся своей серединой и парой её соседей, значит через вершину степени $d$ их проходит $C_d^2$ — и ответ получается одной суммой.

Ориентированный случай

Там степени две: исходящая и входящая. Сумма исходящих равна $m$, а не $2m$: у ориентированного ребра конец только один — тот, куда оно ведёт.

В неориентированном графе 10 вершин и 15 рёбер, петель нет.

Чему равна сумма степеней всех вершин? Введите целое число.

В условии почти всегда написано, чего в графе не бывает. Читать эту строчку надо внимательно: от неё зависит код.

Петля — ребро из вершины в саму себя. К степени оно добавляет двойку, а не единицу: у него два конца, и оба в одной вершине. В списке смежности вершина окажется собственным соседом.

Кратные рёбра — несколько рёбер между одной парой. Список смежности их сохранит, множество пар — нет. Что именно нужно, решает условие.

Если требуется считать пары различными, приводите каждую к одному виду — меньший номер первым:

key = (a, b) if a < b else (b, a)

Без этого ребро $(3, 7)$ и ребро $(7, 3)$ окажутся разными, хотя это одно и то же ребро.

Простой граф — без петель и кратных рёбер. У него число рёбер не превосходит $C_n^2$, и это иногда позволяет сразу отбросить невозможные варианты.

Ребро добавлено в одну сторону. Главная ошибка темы. Программа не падает: список смежности получается, просто он описывает другой граф — ориентированный. Все степени выходят вдвое меньше, ответы неверны, а место ошибки ничем себя не выдаёт. Проверяйте суммой степеней.

Матрица смежности при больших $n$. Программа падает по памяти или не запускается вовсе. Считайте $n^2$ до того, как пишете.

Вершина с номером $n$ не помещается. Списки заводятся на $n$ ячеек вместо $n + 1$, и последняя вершина выходит за границу. Заводите на единицу больше и не думайте об этом.

Забыт случай без рёбер. При $m = 0$ строка с рёбрами пуста, и попытка её разобрать даёт пустой список — но некоторые способы чтения на этом спотыкаются.

Изолированные вершины потеряны. Если строить граф только по рёбрам, вершины без рёбер вообще не появятся. Их надо учитывать отдельно — они существуют, просто ни с кем не связаны.

Как проверять себя

• граф без рёбер — $m = 0$;
• одна вершина — $n = 1$;
• сумма степеней равна $2m$ — на любом тесте;
• граф с изолированной вершиной — она должна попасть в ответ.

Лестница прежняя: пять разминочных, семь основных, три со звёздочкой. Зачёт при десяти решённых.

Обходов графа мы ещё не проходили, и ни одна задача занятия их не требует. Всё решается построением графа и подсчётом степеней — это и есть цель: научиться переводить условие в граф раньше, чем начинать что-то с ним делать.

И заведите привычку: построили граф — проверьте сумму степеней.

Задача: «дан неориентированный граф из $n$ вершин и $m$ рёбер без петель и кратных рёбер; посчитайте, сколько в нём вершин ровно с одним соседом».

Ученик написал:

n, m = map(int, input().split())
flat = list(map(int, input().split()))

adj = [[] for _ in range(n + 1)]
for i in range(0, len(flat), 2):
    adj[flat[i]].append(flat[i + 1])

count = 0
for v in range(1, n + 1):
    if len(adj[v]) == 1:
        count += 1

print(count)

Программа не падает ни на одном тесте и на некоторых даёт правильный ответ.

Постройте вход, на котором она ошибается, объясните, что именно она построила вместо нужного графа, и предложите исправление.