Vladok AC - 8 months ago 82

Java Question

The Task is "You've got a adjacency matrix (nxn). And simple graph. Print YES, if the graph is undirected and NO otherwise." My teacher says that the programm is incorrect. Why?

`import java.util.Scanner;`

public class Graph {

private static Scanner scan;

public static void main(String[] args){

scan = new Scanner(System.in);

final int n = scan.nextInt();

Graph graph = new Graph();

int[][] matrix = graph.createMatrix(n);

boolean truth = graph.checkoriented(matrix);

System.out.println((truth)? "Yes": "No");

scan.close();

}

private boolean checkoriented(int[][] matrix) {

for(int i = 0; i < matrix.length; i++){

for(int j = 0; j < matrix.length; j++){

if(matrix[i][j] == 1){ //look if element on i pow, j column is "1";

boolean way = (matrix[j][i] == 1)? true: false; //if element on j pow i locumn is 1 also

if(!way) return false; // if element on j pow i locumn is 0 graph is oriented

}

}

}

return true;

}

private int[][] createMatrix(int n) {

int[][] matrix = new int[n][n];

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

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

matrix[i][j] = scan.nextInt();

}

}

return matrix;

}

}

Answer

I don't know if it is actually a problem, but if your output should be `YES`

or `NO`

you'd better print these instead of `Yes`

and `No`

here `System.out.println((truth)? "Yes": "No");`

.

P. S. If your graph has a way from the vertex to the same one (I mean `matrix[i][i] = 1`

), your algorithm might consider the graph to be undirected, while it is not.

Source (Stackoverflow)