题解 | #体育课测验(一)#

import java.util.*;
public class Solution {
//     成环即返回false
    //存储有向图
    public ArrayList<ArrayList<Integer>> lists;
    //节点的状态 0：从未访问过 1：正在访问搜索中 2：访问结束
    public int[] visit;
    //标记是否成环，res为false就是成环了
    public boolean res = true;
    public boolean canFinish (int numProject, ArrayList<ArrayList<Integer>> groups) {
        // write code here
        //初始化操作
        lists = new ArrayList<>();
        visit = new int[numProject];
        for(int i = 0;i < numProject;i ++) {
            lists.add(new ArrayList<Integer>());
        }
        //先完成的指向后完成（可能会指向多个后完成的，统统add）
        for(ArrayList<Integer> list:groups) {
            lists.get(list.get(1)).add(list.get(0));
        }
        for(int i = 0;i < numProject;i ++) {
            //成环啦，跳出循环
            if(!res)
                break;
            //遍历到一个没有被搜索过的节点
            if(visit[i] == 0)
                func(i);
        }
        return res;
    }
    public void func(int index) {
        visit[index] = 1;
        //标记成正在搜索中
        ArrayList<Integer> list = lists.get(index);
        //获取到该节点所有指向的节点（该项目需要在被指向的项目们之前完成）
        for(int k : list) {
            //遍历到一个没有被搜索过的节点，深度遍历
            if(visit[k] == 0) {
                func(k);
                //成环啦，返回
                if(!res) 
                    return;
            }else if(visit[k] == 1) {
                //正在搜索的过程中搜索到另一个正在搜索状态的节点，成环
                res = false;//置为false，返回
                return;
            }
        }
        //该节点的状态为搜索已完成
        visit[index] = 2;
    }
}