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

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numProject int整型 
     * @param groups int整型ArrayList<ArrayList<>> 
     * @return bool布尔型
     */
    boolean[] visited;
    boolean[] onPath;
    boolean hasCycle;
    public boolean canFinish (int numProject, ArrayList<ArrayList<Integer>> groups) {
        // write code here
        List<Integer>[] graph = buildGraph(numProject,groups);
        visited = new boolean[numProject];
        onPath = new boolean[numProject];
        for(int i=0;i<numProject;i++){
            traverse(graph,i);
        }
        return !hasCycle;
    }
    
    List<Integer>[] buildGraph(int numProject,ArrayList<ArrayList<Integer>> groups){
        List<Integer>[] graph = new LinkedList[numProject];
        for(int i=0;i<numProject;i++){
            graph[i] = new LinkedList<Integer>();
        }
        for(int j=0;j<groups.size();j++){
            graph[groups.get(j).get(0)].add(groups.get(j).get(1));
        }
        return graph;
    }
    void traverse(List<Integer>[] graph,int s){
        if(onPath[s]) hasCycle=true;
        if(hasCycle||visited[s]) return;
        visited[s]=true;
        onPath[s]=true;
        for(int t:graph[s]){
            traverse(graph,t);
        }
        onPath[s]=false;
    }
}