3981. От матрицы смежности к спискам смежности

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

Вход. В первой строке задано количество вершин графа n (1 ≤ n ≤ 100). Далее следуют n строк по n чисел – матрица смежности. Гарантируется, что в графе нет петель.

Выход.  Выведите n строк – списки смежности графа. В i-ой строке сначала выведите количество рёбер, исходящих из вершины i, а затем – номера вершин, в которые они направлены, в порядке возрастания.

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

РЕШЕНИЕ

графы

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

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

Пример

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

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

Объявим список смежности графа.

vector<vector<int> > g;

Читаем входные данные. Вершины графа нумеруются от 1 до n. Строим список смежности.

scanf("%d", &n);

g.resize(n + 1);

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

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

{

scanf("%d", &val);

if (val) g[i].push_back(j);

}

Выводим список смежности.

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

{

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

for (int x : g[i])

printf(" %d", x);

printf("\n");

}

Java реализация – array of ArrayList

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

ArrayList<Integer>[] g = new ArrayList[n+1]; // unchecked

for (int i = 0; i <= n; i++)

g[i] = new ArrayList<Integer>();

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

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

{

int val = con.nextInt();

if (val == 1) g[i].add(j);

}

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

{

System.out.print(g[i].size());

for (int j = 0; j < g[i].size(); j++)

System.out.print(" " + g[i].get(j));

System.out.println();

}

con.close();

}

}

Java реализация – ArrayList of ArrayList

import java.util.*;

import java.io.*;

public class Main

{

public static void main(String[] args) throws IOException

{

//Scanner con = new Scanner(new FileReader ("3981.in"));

Scanner con = new Scanner(System.in);

int n = con.nextInt();

ArrayList<ArrayList<Integer>> g =

new ArrayList<ArrayList<Integer>>();

for (int i = 0; i <= n; i++)

g.add(new ArrayList<Integer>());

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

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

{

int val = con.nextInt();

if (val == 1) g.get(i).add(j);

}

//System.out.println(g);

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

{

System.out.print(g.get(i).size());

for (int j = 0; j < g.get(i).size(); j++)

System.out.print(" " + g.get(i).get(j));

System.out.println();

}

con.close();

}

}

Python реализация

Читаем количество вершин n. Объявим список смежности g.

n = int(input())

g = [[] for _ in range(n + 1)]

Читаем матрицу смежности и строим список смежности. Вершины графа нумеруются от 1 до n.

for i in range(1, n + 1):

row = list(map(int, input().split()))

for j in range(1, n + 1):

if row[j - 1]:

g[i].append(j)

Выводим список смежности.

for i in range(1, n + 1):

print(len(g[i]), *g[i])