Алгоритмы и структуры данных

Матрица смежности — представление графа

Граф — это структура, состоящая из вершин (узлов) и рёбер, которые соединяют эти вершины. Графы могут использоваться для моделирования взаимосвязей между объектами или для представления сетей. Их часто применяют, чтобы отобразить соединения между городами, людьми или даже абстрактными сущностями.
Графы бывают ориентированными или неориентированными:
  1. Ориентированные графы: Все рёбра имеют направление, то есть “дорога” может вести от одной вершины к другой, но при этом обратного пути может и не быть. Аналогично дороге с односторонним движением. Однако в ориентированном графе можно иметь двустороннюю связь, просто каждая из сторон будет явно указана (как связь между вершинами 5 и 8 в примере).
      2. Yet, it’s possible to have both directions in a directed graph. They are just explicitly marked for that (the connection between vertices 5 and 8 in the graph).
Ориентированный граф с 8 вершинами и 10 рёбрами. Обратите внимание, что у вершин 5 и 8 двусторонняя связь.
Ориентированный граф с 8 вершинами и 10 рёбрами. Обратите внимание, что у вершин 5 и 8 двусторонняя связь.
  1. Неориентированные графы: Рёбра не имеют направления. Если между двумя вершинами есть ребро, то они автоматически связаны в обе стороны.
Неориентированный граф с 8 вершинами и 9 рёбрами
Неориентированный граф с 8 вершинами и 9 рёбрами
Один из способов представить граф — использовать матрицу смежности. Это квадратная матрица, описывающая всю структуру графа. Каждая строка и столбец матрицы соответствуют вершине. Если между двумя вершинами существует ребро, соответствующая ячейка в матрице будет равна 1. В противном случае — 0.
Ниже показан пример матрицы смежности для ориентированного графа, приведённого выше:
g = [
#  1  2  3  4  5  6  7  8
  [0, 1, 0, 1, 0, 0, 0, 0],   # соединения, исходящие из вершины 1
  [0, 0, 0, 0, 1, 0, 0, 0],   # соединения, исходящие из вершины 2
  [0, 1, 0, 0, 0, 0, 0, 0],   # соединения, исходящие из вершины 3
  [0, 0, 0, 0, 0, 0, 0, 0],   # соединения, исходящие из вершины 4
  [0, 0, 0, 0, 0, 1, 0, 1],   # соединения, исходящие из вершины 5
  [0, 0, 0, 1, 0, 0, 1, 0],   # соединения, исходящие из вершины 6
  [0, 0, 0, 0, 0, 0, 0, 1],   # соединения, исходящие из вершины 7
  [0, 0, 0, 0, 1, 0, 0, 0],   # соединения, исходящие из вершины 8
]
Обратите внимание, что для двустороннего ребра (bidirectional edge) в матрице присутствуют единицы в обеих соответствующих позициях.
Также стоит отметить, что мы изменили индексацию вершин. Так, если обратиться к g[0], будет возвращён список всех соединений вершины с индексом 1. Можно было бы использовать матрицу 9×9 вместо 8×8, чтобы индексация в коде совпадала с нумерацией вершин на рисунке, но здесь всё зависит только от вашего выбора 😎.

Задача: рёбра в матрицу смежности

Пусть дан граф с v вершинами и e рёбрами. Требуется получить его матрицу смежности.

Вход

Первая строка входных данных содержит два целых числа v (1 ≤ v ≤ 1000) и e (1 ≤ e ≤ 100 000).
В следующих e строках указаны пары целых чисел v1, v2 (1 ≤ v1, v2 ≤ v), что означает: вершина v1 соединена с вершиной v2 и наоборот.

Выход

Программа должна вывести матрицу смежности данного графа. Значения в каждой строке следует отделять пробелом.

Примеры

Вход
Выход
8 9 1 4 4 6 3 2 2 1 5 2 5 6 8 5 7 6 7 8
0 1 0 1 0 0 0 0 1 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 1 0 0 0 1 0 0 0 1 0 1 0 0 0 1 1 0 1 0 0 0 0 0 0 1 0 1 0 0 0 0 1 0 1 0
 

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 5 MB

To check your solution you need to sign in
Sign in to continue