I wrote this code for a programming assignment given in a course about graphs on Coursera. enter code here. It passes on the test cases given in the question description but fails on one when submitted I'm new to graphs. Can some one help me find the error in this code?
import java.util.ArrayList;
import java.util.Scanner;
import java.util.Iterator;
public class Reachability {
private static boolean[] visited;
private static int reach(ArrayList<Integer>[] adj, int x, int y) {
if(x == y){
return 1;
}
visited[x] = true;
Iterator itr = adj[x].iterator();
while(itr.hasNext()){
x = (int)itr.next();
if(!visited[x]){
return reach(adj,x,y);
}
}
return 0;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
ArrayList<Integer>[] adj = (ArrayList<Integer>[])new ArrayList[n];
for (int i = 0; i < n; i++) {
adj[i] = new ArrayList<Integer>();
}
for (int i = 0; i < m; i++) {
int x, y;
x = scanner.nextInt();
y = scanner.nextInt();
adj[x - 1].add(y - 1);
adj[y - 1].add(x - 1);
}
int x = scanner.nextInt() - 1;
int y = scanner.nextInt() - 1;
visited = new boolean[n];
System.out.println(reach(adj, x, y));
}
}
Given below is the failed test case.
Failed case #6/16: (Wrong answer)
Input: 100 100 27 96 6 9 81 98 21 94 22 68 76 100 8 50 38 86 71 75 32 93 16 50 71 84 6 72 22 58 7 19 19 76 44 75 24 76 31 35 11 89 42 98 63 92 37 38 20 98 45 91 23 53 37 91 76 93 67 90 12 22 43 52 23 56 67 68 1 21 17 83 63 72 30 32 7 91 50 69 38 44 55 89 15 23 11 72 28 42 22 69 56 79 5 83 55 73 13 72 7 93 20 54 21 55 66 89 2 91 18 88 26 64 11 61 28 59 12 86 42 95 17 82 50 66 66 99 40 71 20 40 5 66 92 95 32 46 7 36 44 94 6 31 19 67 26 57 53 84 10 68 28 74 34 94 25 61 71 88 10 89 28 52 72 79 39 73 11 80 44 79 13 77 30 96 30 53 10 39 1 90 40 91 62 71 44 54 15 17 69 74 13 67 24 69 34 96 21 50 20 91 42 46
Your output: 0
Correct output: 1
The problem is that you do an early return from reach() if y cannot be reached via the first unvisited neighbor of x:
return reach(adj,x,y);
What you want to do instead is:
y can be reached then return 1.y cannot be reached then continue with the next neighborThat would read:
if (reach(adj, x, y) == 1)
return 1;
Unrelated comment: You may want to use Iterator<Integer> instead of the raw type Integer. This avoids the cast and compiler warnings.