Задача
Простой неориентированный граф задан матрицей смежности, выведите его представление в виде списка рeбер.
Вводные данные
Первая строка содержит количество вершин $n$ $(1 \leq n \leq 100)$ в графе. Затем идут $n$ строк по $n$ элементов в каждой — описание матрицы смежности.
Выходные данные
Вывести список ребер, упорядоченный по первой вершине в паре вершин, которая описывает ребро.
Тесты
| Входные данные | Выходные данные |
|
$3$ $0$ $1$ $1$ $1$ $0$ $1$ $1$ $1$ $0$ |
$1$ $2$ $1$ $3$ $2$ $3$ |
|
$3$ $0$ $1$ $0$ $1$ $0$ $0$ $0$ $0$ $0$ |
$1$ $2$ |
|
$5$ $0$ $1$ $0$ $1$ $1$ $1$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $0$ $1$ $0$ $0$ $0$ $0$ $1$ $0$ $0$ $0$ $0$ |
$1$ $2$ $1$ $4$ $1$ $5$ |
Код программы
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
import java.util.*; import java.lang.*; import java.io.*; class Main { public static void main (String[] args) throws java.lang.Exception { Scanner in = new Scanner(System.in); int n = in.nextInt(); int[][] x = new int[n][n]; for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { x[i][j] = in.nextInt(); } } for(int i = 0; i < n; i++) { for(int j = i; j < n; j++) { if(x[i][j] == 1) System.out.println((i+1) + " " + (j+1)); } } } } |
Решение задачи
Для решения задачи вводим матрицу смежности. Далее в цикле проходим верхнюю треугольную часть матрицы смежности и выписываем индексы (из какой вершины и в какую другую вершину идет ребро, т.е. получаем список ребер). Задача решена.
Ссылки
Условие задачи на e-olymp
Код решения на ideone.com