Vladok AC Vladok AC - 15 days ago 5
Java Question

Check if simple graph is oriented?

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.