# My DFS & BFS Java Solution

• ``````public class Solution {
// bfs solution
public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses == 0 || prerequisites.length == 0) {
return true;
}

boolean[] isVisited = new boolean[numCourses];
Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
Map<Integer, Integer> inDegree = new HashMap<Integer, Integer>();

constructGraph(numCourses, prerequisites, graph, inDegree);

for (int i = 0; i < numCourses; i++) {
if (!inDegree.containsKey(i)) {
q.offer(i);
isVisited[i] = true;
}
}

while (!q.isEmpty()) {
int tmp = q.poll();
isVisited[tmp] = true;
List<Integer> neighbors = graph.get(tmp);
for (int next : neighbors) {
inDegree.put(next, inDegree.get(next) - 1);
if (inDegree.get(next) == 0) {
q.offer(next);
}
}
}

for (int i = 0; i < numCourses; i++) {
if (!isVisited[i]) {
return false;
}
}

return true;
}

private void constructGraph(int numCourses, int[][] prerequisites,
Map<Integer, List<Integer>> graph, Map<Integer, Integer> inDegree) {
for (int i = 0; i < numCourses; i++) {
List<Integer> list = new ArrayList<Integer>();
graph.put(i, list);
}

for (int i = 0; i < prerequisites.length; i++) {
int end = prerequisites[i][1];
if (inDegree.containsKey(end)) {
inDegree.put(end, inDegree.get(end) + 1);
} else {
inDegree.put(end, 1);
}
}

for (int i = 0; i < prerequisites.length; i++) {
int key = prerequisites[i][0];
int neighbor = prerequisites[i][1];
}
}}

public class Solution {
// dfs solution
// status
private static int UNVISITED = 0;
private static int VISITED = 1;
private static int PASSED = 2;

public boolean canFinish(int numCourses, int[][] prerequisites) {
if (numCourses == 0 || prerequisites.length == 0) {
return true;
}

Map<Integer, List<Integer>> graph = new HashMap<Integer, List<Integer>>();
int[] status = new int[numCourses];
Arrays.fill(status, UNVISITED);

constructGraph(numCourses, prerequisites, graph);

while (!isFinished(numCourses, status)) {
int start = 0;
for (int i = 0; i < numCourses; i++) {
if (status[i] == UNVISITED) {
start = i;
}
}
if (!dfs(graph, status, start)) {
return false;
}
}

return true;
}

private boolean dfs(Map<Integer, List<Integer>> graph, int[] status, int start) {
if (status[start] == VISITED) {
return true;
}

// a loop in graph
if (status[start] == PASSED) {
return false;
}

status[start] = PASSED;
List<Integer> nextList = graph.get(start);
for (int next : nextList) {
if (!dfs(graph, status, next)) {
return false;
}
}
status[start] = VISITED;
return true;
}

private boolean isFinished(int numCourses, int[] status) {
for (int i = 0; i < numCourses; i++) {
if (status[i] == UNVISITED) {
return false;
}
}
return true;
}

private void constructGraph(int numCourses, int[][] prerequisites, Map<Integer, List<Integer>> graph) {
for (int i = 0; i < numCourses; i++) {
List<Integer> list = new ArrayList<Integer>();
graph.put(i, list);
}

for (int i = 0; i < prerequisites.length; i++) {
int key = prerequisites[i][0];
int neighbor = prerequisites[i][1];