public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList[] graph = new ArrayList[numCourses];
int[] visited = new int[numCourses];
for(int i = 0; i < numCourses; i++){
graph[i] = new ArrayList<Integer>();
}
for(int[] num : prerequisites){
int parent = num[1];
int child = num[0];
graph[parent].add(child);
}
for(int i = 0; i < numCourses; i++){
if(visited[i] == 0 && hasCycle(i, visited, graph)) return false;
}
return true;
}
private boolean hasCycle(int cur, int[] visited, ArrayList[] graph){
visited[cur] = 1;
boolean hasCycle = false;
for(int i = 0; i < graph[cur].size(); i++){
int next = (int) graph[cur].get(i);
if(visited[next] == 1) return true;
else if(visited[next] == 0){
hasCycle = hasCycle || hasCycle(next, visited, graph);
}
}
visited[cur] = 2;
return hasCycle;
}
}
public class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
ArrayList[] graph = new ArrayList[numCourses];
int[] indegree = new int[numCourses];
for(int i = 0; i < numCourses; i++){
graph[i] = new ArrayList<Integer>();
}
for(int[] num : prerequisites){
int parent = num[1];
int child = num[0];
graph[parent].add(child);
indegree[child] ++;
}
Queue<Integer> queue = new LinkedList<>();
for(int i = 0; i < numCourses; i++){
if(indegree[i] == 0) queue.offer(i);
}
int visitedCount = 0;
while(!queue.isEmpty()){
int cur = queue.poll();
visitedCount ++;
for(int i = 0; i < graph[cur].size(); i++){
int next = (int) graph[cur].get(i);
indegree[next] --;
if(indegree[next] == 0){
queue.offer(next);
}
}
}
return (visitedCount == numCourses);
}
}
public class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] rst = new int[numCourses];
int[] indegree = new int[numCourses];
ArrayList[] graph = new ArrayList[numCourses];
for(int i = 0; i < numCourses; i++){
graph[i] = new ArrayList();
}
for(int[] edge : prerequisites){
int parent = edge[1];
int child = edge[0];
graph[parent].add(child);
indegree[child] ++;
}
Queue<Integer> queue = new LinkedList<Integer>();
for(int i = 0; i < numCourses; i++){
if(indegree[i] == 0) queue.offer(i);
}
int index = 0;
int visitedCount = 0;
while(!queue.isEmpty()){
int cur = queue.poll();
rst[index ++] = cur;
visitedCount ++;
for(int i = 0; i < graph[cur].size(); i++){
int next = (int) graph[cur].get(i);
indegree[next] --;
if(indegree[next] == 0){
queue.offer(next);
}
}
}
return (visitedCount == numCourses) ? rst : new int[0];
}
}