package question;

import java.util.*;

public class Question207 {
 //广度优先
 public boolean canFinish(int numCourses, int[][] prerequisites) {
 int[] adCnt = new int[numCourses];
 List<Integer>[] adList = new List[numCourses];
 for (int i = 0; i < numCourses; i++) {
 adList[i]=new ArrayList<>();
 }
 for (int[] prerequisite : prerequisites) {
 adCnt[prerequisite[0]]++;
 adList[prerequisite[1]].add(prerequisite[0]);
 }
 Queue<Integer> queue = new LinkedList<>();
 int x=0;
 for (int i = 0; i < adCnt.length; i++) {
 if (adCnt[i]==0)
 queue.offer(i);
 }
 while (!queue.isEmpty()) {
 Integer pre = queue.poll();
 x++;
 for (int i = 0; i < adList[pre].size(); i++) {
 int k = adList[pre].get(i);
 adCnt[k]--;
 if (adCnt[k]==0) queue.add(k);
 }
 }
 return x == numCourses;
 }

 List<List<Integer>> adList;
 int[] status;
 boolean res;
 public boolean canFinish2(int numCourses, int[][] prerequisites) {
 status=new int[numCourses];
 adList=new ArrayList<>();
 res=true;
 for (int i = 0; i < numCourses; i++) {
 adList.add(new ArrayList<>());
 }
 for (int[] prerequisite : prerequisites) {
 adList.get(prerequisite[1]).add(prerequisite[0]);
 }
 for (int i = 0; i < numCourses && res; i++) {
 if (status[i]==0) dfs(i);
 }
 return res;
 }

 private void dfs(int x) {
 status[x]=1;
 for (Integer k : adList.get(x)) {
 if (status[k]==0) {
 dfs(k);
 if (!res) return;
 } else if (status[k]==1) {
 res=false;
 return;
 }
 }
 status[x]=2;
 }
}