Problem 2.1.7c

P217.java

public class P217 {
	public static void main(String[] args) throws Exception {
		// Example 
		boolean[][] r = {
			{false, false, false, true, false, false},
			{false, false, true, false, false, false},
			{false, true, false, false, false, false},
			{false, false, true, false, false, false},
			{false, false, false, false, false, true},
			{false, false, false, true, false, false},
		};
		// Test cases
		// 3 -> 5 = False
		// 5 -> 3 = True
		// 5 -> 1 = True
		System.out.println(memberOfS(1, 5, r));
	}
	// Test if (a, b) is a member of S.
	private static boolean memberOfS(int a, int b, boolean[][] r) throws Exception {
		boolean[] visited = new boolean[r.length];
		return search(r, visited, a, b);
	}
	// Helper argmax function
	private static int argmax(boolean[] arr) throws Exception {
		if (arr.length < 0) {
			throw new Exception("Empty array passed to argmax");
		}
		// Find the true value and return it's index
		for (int i = 0; i < arr.length; i++) {
			if (arr[i]) {
				return i;
			}
		}

		throw new Exception("No true found in array");
	}
	// Takes the boolean array, starting and ending people.
	// Returns whether there is a path between a and b.
	private static boolean search(boolean[][] arr, boolean[] visited, int a, int b) throws Exception {
		// Mark person as visited
		visited[a] = true;
		// Use argmax function to find next person
		int next = argmax(arr[a]);
		// If we have already visited the next person
		// then we are in a loop and should return false.
		if (visited[next]) {
			return false;
		// If we found the target then return true.
		} else if (next == b) {
			return true;
		}
		// Call search recursively
		return search(arr, visited, next, b);
	}
}