Список смежности — представление графов
Один из самых популярных способов описания графов — это списки смежности. Такой список представляет собой массив списков, где каждый элемент массива соответствует вершине, а сам список, связанный с этой вершиной, содержит все вершины, которые с ней непосредственно связаны.
Исходя из направленного графа, показанного на рисунке, мы можем составить следующий список смежности:
g = [
[], # Пропускаем вершину 0
[2, 4], # Вершина 1
[5], # Вершина 2
[2], # Вершина 3
[], # Вершина 4
[6, 8], # Вершина 5
[4, 7], # Вершина 6
[8], # Вершина 7
[5], # Вершина 8
]
Как можете заметить, представление графа в виде списка смежности значительно компактнее по сравнению с матрицей смежности, поскольку в нашем примере не так много рёбер. Но если рёбер становится очень много, то матрица смежности может оказаться более эффективным способом хранения графа.
Задание: Рёбра в список смежности
Пусть дан неориентированный граф с
v вершинами и e рёбрами. Требуется построить его список смежности.Входные данные
В первой строке входных данных находятся два целых числа
v (1 ≤ v ≤ 100 000) и e (1 ≤ e ≤ 100 000).В следующих
e строках приведены пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), означающие, что вершина v1 соединена с вершиной v2, а вершина v2 — с v1.Выходные данные
Программа должна вывести список смежности для заданного графа. Каждая строка должна начинаться с номера вершины, за которым следует двоеточие (
:), а затем — все вершины, смежные с ней. Связанные вершины в строке отделяются друг от друга пробелами. Порядок вывода вершин и их соседей может быть произвольным.Примеры
Входные данные | Выходные данные |
8 9
1 4
4 6
3 2
2 1
5 2
5 6
8 5
7 6
7 8 | 1: 2 4
2: 1 3 5
3: 2
4: 1 6
5: 2 6 8
6: 4 7 5
7: 8 6
8: 5 7 |
Пояснение
Constraints
Time limit: 2.2 seconds
Memory limit: 512 MB
Output limit: 1 MB