3982. От списков смежности к матрице смежности

Простой ориентированный граф задан в виде списков смежности. Выведите его представление в виде матрицы смежности.

Вход. В первой строке содержится количество вершин n (1 ≤ n ≤ 100). Далее идут n строк. В i-ой строке содержится описание всех рёбер, исходящих из i-ой вершины. Описание начинается количеством исходящих рёбер. Далее следуют номера вершин, в которые эти рёбра идут. Все вершины нумеруются натуральными числами от 1 до n.

Выход. Выведите матрицу смежности ориентированного графа.

Пример входа	Пример выхода
3 2 2 3 0 1 2	0 1 1 0 0 0 0 1 0

РЕШЕНИЕ

графы

Анализ алгоритма

По списку смежности строим матрицу смежности. Затем выводим ее.

Пример

Граф из примера имеет следующий вид.

Реализация алгоритма

Объявим матрицу смежности.

#define MAX 110

int g[MAX][MAX];

Читаем количество вершин графа n.

scanf("%d", &n);

Читаем список смежности и строим матрицу смежности.

for (i = 1; i <= n; i++)

{

Вершина i соединена с k другими вершинами.

scanf("%d", &k);

for (j = 0; j < k; j++)

{

Граф содержит ориентированное ребро (i, to).

scanf("%d", &to);

g[i][to] = 1;

}

}

Выводим матрицу смежности.

for (i = 1; i <= n; i++)

{

for (j = 1; j <= n; j++)

printf("%d ", g[i][j]);

printf("\n");

}