Задача
Простой ориентированный граф задан списком ребер. Требуется вывести его представление в виде матрицы смежности.
Входные данные
Во входном потоке заданы два числа $n$ и $m$ — количество вершин и ребер ($1 \leqslant n \leqslant 100$, $1 \leqslant m \leqslant n(n-1)$). Далее следуют $m$ пар чисел — ориентированные ребра графа.
Выходные данные
Выведите матрицу смежности заданного графа: $n$ строк по $n$ чисел, где элемент $(i, j)$ равен единице, если из вершины $i$ существует ребро в вершину $j$, и нулю в противном случае.
Пример
стандартный ввод стандартный вывод
5 3 0 0 1 0 0
1 3 0 0 1 0 0
2 3 0 0 0 0 0
5 2 0 0 0 0 0
0 1 0 0 0
Ограничения
- Время: 1 секунда
- Память: 256 мегабайт
Редакционный разбор
Создаём квадратную таблицу $n \times n$, заполненную нулями. Далее читаем каждое ребро $(u, v)$ и выставляем в матрице элемент $a_{u,v} = 1$. Поскольку вершины нумеруются с единицы, удобнее хранить матрицу в виде массива `vector<vector> a(n, vector(n))` и обращаться по индексам `u-1`, `v-1`.
Вывод заключается в печати всех строк матрицы. Даже если каких-то рёбер нет, соответствующие нули мы печатаем явно, поэтому итоговая сложность — $O(n^2)$, что укладывается в ограничения (значения $m$ на порядок меньше $n^2$, но мы всё равно обязаны вывести весь квадрат из $n^2$ чисел).
Ниже приведён опорный код:
```cpp
int n, m;
cin >> n >> m;
vector<vector> a(n, vector(n));
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
a[u - 1][v - 1] = 1;
}
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
cout << a[i][j] << (j + 1 == n ? '\n' : ' ');
}
}
```
Временная и по памяти сложность — $O(n^2)$.
</details>
### Mentioned by
- [DFS1 — параллель B'](/dsa-notes/bp2025/contests/dfs1/){: .dsa-mention } — A: 1. От списка ребер к матрице смежности
- [Каталог задач](/dsa-notes/problems/){: .dsa-mention } — A: 1. От списка ребер к матрице смежности
