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

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

Вход. Первая строка содержит количество вершин n (1 ≤ n ≤ 100) в графе.  Следующие 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();

}

}