解法

dfs和bfs

dfs

深度优先遍历，也就是没环的话继续尝试其他的节点，有环的话就层层返回false，大概的情况就是下面

以当前节点作为传入节点，然后遍历这个节点的全部相邻进入的节点，
有一个不符合条件，就返回false，遍历完了全部才返回true

在这里需要设置三个标志位，0，1，-1
0表示没有访问过
1表示当前的递归访问过了
-1表示其他的递归访问过了

 public static boolean canFinish(int numCourses, int[][] prerequisites) {
        //0表示没有访问过，-1表示已经访问过
        int[] flag = new int[numCourses];
        ArrayList<ArrayList<Integer>> graph = new ArrayList<>();
        //形成图
        for (int i = 0; i < numCourses; i++) {
            graph.add(new ArrayList<>());
        }
        for(int i=0;i<numCourses;i++)
        {
            if(!f(i,graph,flag)) return false;
        }
        return true;
    }
    //以p作为起点，是否有环
    public static boolean f(int p, ArrayList<ArrayList<Integer>> graph, int[] flag) {
        //base case
        if(flag[p]==-1) return false;//自己的
        if(flag[p]==1) return true;//其他的
        flag[p]=-1;
        for(Integer e:graph.get(p))
        {
            if(!f(e,graph,flag)) return false;
        }
        flag[p]=1;
        return true;
    }

需要注意的位置就是flag置为1和-1的时机

bfs

宽度优先遍历就是通过队列的参与，选择入度为0的入队，开始遍历相邻的节点，直到相邻的节点入度变成0了就可以入队了

```
/*
prerequisites 多维两列数组
第一列为被进入的
第二列为进入的
*/
public static boolean canFinish(int numCourses, int[][] prerequisites) {

    int[] in=new int[numCourses];//入度表
    ArrayList<ArrayList<Integer>> graph=new ArrayList<>();//图
    LinkedList<Integer> queue=new LinkedList<>();
    //初始化图
    for(int i=0;i<numCourses;i++)
    {
        graph.add(new ArrayList<>());
    }
    //形成图和入度表
    for(int i=0;i<prerequisites.length;i++)
    {
        in[prerequisites[i][0]]++;
        graph.get(prerequisites[i][1]).add(prerequisites[i][0]);
    }
    for(int i=0;i<numCourses;i++)
    {
        if(in[i]==0) queue.addLast(i);
    }
    while(!queue.isEmpty())
    {
        int temp=queue.pollFirst();
        numCourses--;
        ArrayList<Integer> tempGraph=graph.get(temp);
        for(Integer e:tempGraph)
        {
            if(--in[e]==0) queue.addLast(e);
        }
    }
    return numCourses==0;
}

``