2471. От матрицы смежности к списку рёбер

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

Вход. Первая строка содержит количество вершин n (1 ≤ n ≤ 100) в графе. Затем идут n строк по n элементов в каждой – описание матрицы смежности.

Выход. Вывести список ребер, упорядоченный по первой вершине в паре вершин, которая описывает ребро.

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

РЕШЕНИЕ

графы

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

Будем выводить список ребер «на лету», обрабатывая матрицу смежности построчно сверху вниз, а каждую ее строку слева направо. Для каждой единицы в матрице смежности выводим пару вершин, задающих соответствующее ребро. Пары вершин как раз будут упорядочены по первой вершине.

Пример

Граф, приведенный в примере, имеет вид:

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

Читаем матрицу смежности графа. Поскольку граф неориентированный, то будем выводить лишь те ребра (i, j), для которых i < j.

scanf("%d",&n);

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

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

{

scanf("%d",&val);

if (i < j && val == 1)

printf("%d %d\n",i,j);

}

Java реализация

import java.util.*;

public class Main

{

public static void main(String[] args)

{

Scanner con = new Scanner(System.in);

int n = con.nextInt();

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

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

{

int val = con.nextInt();

if (i < j && val == 1)

System.out.println(i + " " + j);

}

con.close();

}

}