Списки смежности из входных данных
Стройте граф, который задают на соревнованиях
«Списки смежности из входных данных» — бесплатный урок Competitive Programming Academy на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения Competitive Programming Academy, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс Competitive Programming Academy содержит 4 уроков всего.
Что такое граф на самом деле
Граф — это всего лишь точки, называемые вершинами, соединённые линиями, называемыми рёбрами. Города, соединённые дорогами, — знакомый вам пример графа. 🗺️
Вершины и рёбра
Каждая вершина — это некоторый объект, а каждое ребро сообщает, что две вершины соединены. В задачах соревнований вершины обычно нумеруются от 1 до n.
Список смежности
Основной способ хранения графа в задачах соревнований — список смежности: для каждой вершины хранится список её непосредственных соседей.
adj = [[] for _ in range(n + 1)]Почему не матрица
Матрица использует n в квадрате ячеек памяти, что становится непрактичным при больших n. Список смежности хранит только существующие рёбра, поэтому лучше масштабируется.
Чтение первой строки
Большинство входных данных начинается с двух чисел: n вершин и m рёбер. Сначала прочитайте их, чтобы знать, сколько рёбер ожидать.
n, m = map(int, input().split())Одно ребро в каждой строке
Каждая из следующих m строк содержит пару u v. Это единственное ребро означает, что u и v напрямую соединены.
u, v = map(int, input().split())Неориентированный граф — это оба направления
Для неориентированного ребра добавьте связь в обоих направлениях. Можно пройти из u в v и из v в u.
adj[u].append(v)
adj[v].append(u)Ориентированный граф — это одно направление
Для ориентированного ребра сохраните только направление из u в v. Внимательно читайте условие, чтобы определить тип графа.
adj[u].append(v)Построение в цикле
Выполните цикл m раз, считайте каждую пару и заполните списки. После завершения цикла ваш список смежности будет содержать весь граф.
for _ in range(m):
u, v = map(int, input().split())
adj[u].append(v)
adj[v].append(u)Индексация с 1 и с 0
Если вершины начинаются с 1, задайте размер списка равным n плюс 1, чтобы индекс n был допустим. Путаница в индексации приводит к незаметным ошибкам.
Обход соседей вершины
После построения графа исследовать его просто: переберите список смежности вершины, чтобы за один шаг обратиться к каждому соседу.
for nb in adj[u]:
print(nb)Быстрая проверка
Вы прочитали неориентированное ребро u v. Что нужно сохранить?
Повторение
Теперь вы умеете строить граф как список смежности: считывать n и m, перебирать рёбра и добавлять оба направления для неориентированного графа. 🎉
Часто задаваемые вопросы
Урок «Списки смежности из входных данных» бесплатный?
Да — полный текст урока «Списки смежности из входных данных» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс Competitive Programming Academy, подпишись на CoddyKit PRO. Курс Competitive Programming Academy содержит 4 уроков всего.
Чему я научусь в уроке «Списки смежности из входных данных»?
Стройте граф, который задают на соревнованиях Ты практикуешь Competitive Programming Academy с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать Competitive Programming Academy?
Предыдущий опыт не требуется. Competitive Programming Academy на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Списки смежности из входных данных»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке Competitive Programming Academy?
Да. Каждый урок Competitive Programming Academy включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Списки смежности из входных данных
- BFS для кратчайших невзвешенных путей
- DFS, рекурсия и итеративные стеки
- Связные компоненты и заливка