2470. Проверка на неориентированность

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

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

Выход. Вывести YES, если граф простой неориентированный, и NO в противном случае.

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

РЕШЕНИЕ

графы

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

Граф называется простым, если он не содержит петель и кратных ребер. Для того чтобы матрица смежности принадлежала неориентированному графу, необходимо чтобы она была симметрична относительно главной диагонали.

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

Матрицу смежности графа будем хранить в массиве m.

#define MAX 101

int m[MAX][MAX];

Читаем входной граф. Если он содержит петлю (m[i][i] = 1 для некоторого значения i), то не является простым.

scanf("%d",&n);

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

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

{

scanf("%d",&m[i][j]);

if ((i == j) && (m[i][j]))

{

printf("NO\n"); return 0;

}

}

Проверяем матрицу на симметричность относительно главной диагонали.

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

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

if (m[i][j] != m[j][i])

{

printf("NO\n"); return 0;

}

printf("YES\n");

Java реализация

import java.util.*;

import java.io.*;

public class Main

{

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

{

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

Scanner con = new Scanner(System.in);

int n = con.nextInt();

int m[][] = new int[n][n];

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

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

{

m[i][j] = con.nextInt();

if ((i == j) && (m[i][j] == 1))

{

System.out.println("NO");

return;

}

}

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

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

if (m[i][j] != m[j][i])

{

System.out.println("NO");

return;

}

System.out.println("YES");

con.close();

}

}